{"id":160,"date":"2017-12-22T18:11:13","date_gmt":"2017-12-22T18:11:13","guid":{"rendered":"http:\/\/sites.rutgers.edu\/professor-example\/?page_id=160"},"modified":"2025-08-22T15:27:16","modified_gmt":"2025-08-22T15:27:16","slug":"courses","status":"publish","type":"page","link":"https:\/\/sites.rutgers.edu\/jie-gao\/courses\/","title":{"rendered":"Courses"},"content":{"rendered":"<h3>Fall 2025<\/h3>\n<h6><strong>CS529 &#8211; Computational Geometry<\/strong><\/h6>\n<p>ARC-333 Tuesday Thursday 3:50pm-5:10pm<\/p>\n<p>This course covers fundamental algorithmic problems associated with geometric computations, including convex hulls, polygons, Voronoi diagrams, triangulation, intersection, range queries, visibility, arrangements, and motion planning for robotics. It also covers algorithmic methods used in geometric computation such as plane sweep, incremental insertion, randomization, divide-and-conquer, etc.\u00a0 Students are expected to have undergraduate level of data structures and algorithms. The course will be counted for breadth requirement (category A) for both PhD and MS program.<\/p>\n<h3>Spring 2024<\/h3>\n<h6><strong>CS514 &#8211; Design and Analysis of Data Structures and Algorithms II<\/strong><\/h6>\n<p>ARC 205 Tuesday 12:10-3:10pm.<\/p>\n<p>Geometric Algorithms<\/p>\n<p>In this course we consider geometry broadly defined, starting from algorithms that handle points, lines, polygons, etc, and move on to geometric structures embedded in physical spaces and real-world data and applications. In terms of algorithms we ask questions such as why classical optimization problems in a geometric setting are easier, what geometric properties can one define on a graph and how that can help with problem solving. We will discuss problems that involve distances, dimensionality and navigation. We also move beyond the notions of geometry (i.e., coordinates, distances, shapes) and talk about topology (connectivity, holes, voids).\u00a0 Students are expected to have a solid algorithm foundation and no background in computational geometry is assumed.<\/p>\n<p>Sample topics:<\/p>\n<ul>\n<li>Convexity, Radon Lemma, Helly Theorem<\/li>\n<li>Low-dim LP and LP-type problems<\/li>\n<li>Power of Grid, linear time closest pair, Locality sensitive hashing<\/li>\n<li>Grid with random shifts, unit disk cover<\/li>\n<li>VC-dimension, eps-net and eps-approximation<\/li>\n<li>Geometric set cover, reweighting techniques<\/li>\n<li>(Euclidean) dimension reduction, MDS, Johnson Linderstrauss Lemma<\/li>\n<li>(Non-Euclidean) dimension reduction, Isomap,<\/li>\n<li>Bourgain theorem, embedding intro tree metrics<\/li>\n<li>Graphs of bounded doubling dimension<\/li>\n<li>Kleinberg&#8217;s small world model, greedy navigation, distance estimation<\/li>\n<li>Quad tree, well-separated pair decomposition<\/li>\n<li>Geometric spanners<\/li>\n<li>Geometric intersection graphs, planar graphs<\/li>\n<\/ul>\n<h3>Fall 2023<\/h3>\n<h6><strong>CS344 &#8211; Design and Analysis of Computer Algorithms<\/strong><\/h6>\n<h3>Spring 2023<\/h3>\n<h6><strong>CS205 &#8211; Introduction to Discrete Structures I<\/strong><\/h6>\n<h3>Fall 2022<\/h3>\n<h6><strong>CS513 &#8211; Design and Analysis of Data Structures and Algorithms<\/strong><\/h6>\n<h3>Spring 2022<\/h3>\n<h6><strong>CS513 &#8211; Design and Analysis of Data Structures and Algorithms<\/strong><\/h6>\n<h3>Fall 2021<\/h3>\n<h6><strong>CS205 &#8211; Introduction to Discrete Structures I<\/strong><\/h6>\n<h3>Spring 2021<\/h3>\n<h6><strong>CS513 &#8211; Design and Analysis of Data Structures and Algorithms<\/strong><\/h6>\n<h3>Fall 2020<\/h3>\n<h6><strong>CS205 &#8211; Introduction to Discrete Structures I<\/strong><\/h6>\n<p><a href=\"https:\/\/sites.google.com\/scarletmail.rutgers.edu\/cs205\/home\">Course Link<\/a><\/p>\n<h3>Spring 2020<\/h3>\n<h6><strong>CS513 &#8211; Design and Analysis of Data Structures and Algorithms<\/strong><\/h6>\n<p><a href=\"https:\/\/sites.google.com\/scarletmail.rutgers.edu\/cs513\/home\">Course Link<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Fall 2025 CS529 &#8211; Computational Geometry ARC-333 Tuesday Thursday 3:50pm-5:10pm This course covers fundamental algorithmic problems associated with geometric computations, including convex hulls, polygons, Voronoi diagrams, triangulation, intersection, range queries, &hellip; <a href=\"https:\/\/sites.rutgers.edu\/jie-gao\/courses\/\" class=\"\">Read More<\/a><\/p>\n","protected":false},"author":11,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"template-custom.php","meta":{"_acf_changed":false,"footnotes":""},"class_list":["post-160","page","type-page","status-publish","hentry"],"acf":[],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v23.5 - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>Courses - Jie Gao<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/sites.rutgers.edu\/jie-gao\/courses\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Courses - Jie Gao\" \/>\n<meta property=\"og:description\" content=\"Fall 2025 CS529 &#8211; Computational Geometry ARC-333 Tuesday Thursday 3:50pm-5:10pm This course covers fundamental algorithmic problems associated with geometric computations, including convex hulls, polygons, Voronoi diagrams, triangulation, intersection, range queries, &hellip; Read More\" \/>\n<meta property=\"og:url\" content=\"https:\/\/sites.rutgers.edu\/jie-gao\/courses\/\" \/>\n<meta property=\"og:site_name\" content=\"Jie Gao\" \/>\n<meta property=\"article:modified_time\" content=\"2025-08-22T15:27:16+00:00\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data1\" content=\"2 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"WebPage\",\"@id\":\"https:\/\/sites.rutgers.edu\/jie-gao\/courses\/\",\"url\":\"https:\/\/sites.rutgers.edu\/jie-gao\/courses\/\",\"name\":\"Courses - Jie Gao\",\"isPartOf\":{\"@id\":\"https:\/\/sites.rutgers.edu\/jie-gao\/#website\"},\"datePublished\":\"2017-12-22T18:11:13+00:00\",\"dateModified\":\"2025-08-22T15:27:16+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/sites.rutgers.edu\/jie-gao\/courses\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/sites.rutgers.edu\/jie-gao\/courses\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/sites.rutgers.edu\/jie-gao\/courses\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/sites.rutgers.edu\/jie-gao\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Courses\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/sites.rutgers.edu\/jie-gao\/#website\",\"url\":\"https:\/\/sites.rutgers.edu\/jie-gao\/\",\"name\":\"Jie Gao\",\"description\":\"\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/sites.rutgers.edu\/jie-gao\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Courses - Jie Gao","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/sites.rutgers.edu\/jie-gao\/courses\/","og_locale":"en_US","og_type":"article","og_title":"Courses - Jie Gao","og_description":"Fall 2025 CS529 &#8211; Computational Geometry ARC-333 Tuesday Thursday 3:50pm-5:10pm This course covers fundamental algorithmic problems associated with geometric computations, including convex hulls, polygons, Voronoi diagrams, triangulation, intersection, range queries, &hellip; Read More","og_url":"https:\/\/sites.rutgers.edu\/jie-gao\/courses\/","og_site_name":"Jie Gao","article_modified_time":"2025-08-22T15:27:16+00:00","twitter_card":"summary_large_image","twitter_misc":{"Est. reading time":"2 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebPage","@id":"https:\/\/sites.rutgers.edu\/jie-gao\/courses\/","url":"https:\/\/sites.rutgers.edu\/jie-gao\/courses\/","name":"Courses - Jie Gao","isPartOf":{"@id":"https:\/\/sites.rutgers.edu\/jie-gao\/#website"},"datePublished":"2017-12-22T18:11:13+00:00","dateModified":"2025-08-22T15:27:16+00:00","breadcrumb":{"@id":"https:\/\/sites.rutgers.edu\/jie-gao\/courses\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/sites.rutgers.edu\/jie-gao\/courses\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/sites.rutgers.edu\/jie-gao\/courses\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/sites.rutgers.edu\/jie-gao\/"},{"@type":"ListItem","position":2,"name":"Courses"}]},{"@type":"WebSite","@id":"https:\/\/sites.rutgers.edu\/jie-gao\/#website","url":"https:\/\/sites.rutgers.edu\/jie-gao\/","name":"Jie Gao","description":"","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/sites.rutgers.edu\/jie-gao\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"}]}},"_links":{"self":[{"href":"https:\/\/sites.rutgers.edu\/jie-gao\/wp-json\/wp\/v2\/pages\/160"}],"collection":[{"href":"https:\/\/sites.rutgers.edu\/jie-gao\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/sites.rutgers.edu\/jie-gao\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/sites.rutgers.edu\/jie-gao\/wp-json\/wp\/v2\/users\/11"}],"replies":[{"embeddable":true,"href":"https:\/\/sites.rutgers.edu\/jie-gao\/wp-json\/wp\/v2\/comments?post=160"}],"version-history":[{"count":23,"href":"https:\/\/sites.rutgers.edu\/jie-gao\/wp-json\/wp\/v2\/pages\/160\/revisions"}],"predecessor-version":[{"id":909,"href":"https:\/\/sites.rutgers.edu\/jie-gao\/wp-json\/wp\/v2\/pages\/160\/revisions\/909"}],"wp:attachment":[{"href":"https:\/\/sites.rutgers.edu\/jie-gao\/wp-json\/wp\/v2\/media?parent=160"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}