{"id":43,"date":"2015-08-18T14:15:30","date_gmt":"2015-08-18T18:15:30","guid":{"rendered":"https:\/\/courses.bowdoin.edu\/computer-science-2200\/?page_id=43"},"modified":"2015-10-07T15:55:25","modified_gmt":"2015-10-07T19:55:25","slug":"schedule","status":"publish","type":"page","link":"https:\/\/courses.bowdoin.edu\/computer-science-2200\/schedule\/","title":{"rendered":"Schedule"},"content":{"rendered":"<p>This schedule is tentative, and will be updated as the semester progresses.<\/p>\n<h2>Week 1<\/h2>\n<ul>\n<li><strong>Topic:<\/strong> Class intro. Warmup with searching (linear and binary) and sorting (bubble sort, insertion sort, selection sort).\u00a0Analysis: The RAM model. Asymptotic analysis and asymptotic notation. Case studies.<br \/>\nNotes: <a href=\"https:\/\/courses.bowdoin.edu\/computer-science-2200\/wp-content\/uploads\/sites\/106\/2015\/08\/L-intro.pdf\">L-intro<\/a>\u00a0| <a href=\"https:\/\/courses.bowdoin.edu\/computer-science-2200\/wp-content\/uploads\/sites\/106\/2015\/08\/ex-bubblesort.pdf\">ex-bubblesort<\/a>\u00a0|\u00a0 <a href=\"https:\/\/courses.bowdoin.edu\/computer-science-2200\/wp-content\/uploads\/sites\/106\/2015\/08\/ex-selsort.pdf\">ex-selsort<\/a>\u00a0|\u00a0 <a href=\"https:\/\/courses.bowdoin.edu\/computer-science-2200\/wp-content\/uploads\/sites\/106\/2015\/08\/L-analysis.pdf\">L-analysis<\/a>\u00a0| <a href=\"https:\/\/courses.bowdoin.edu\/computer-science-2200\/wp-content\/uploads\/sites\/106\/2015\/08\/ex-inssort.pdf\">ex-inssort<\/a>\u00a0| <a href=\"https:\/\/courses.bowdoin.edu\/computer-science-2200\/wp-content\/uploads\/sites\/106\/2015\/08\/ex-analysis1.pdf\">ex-analysis1<\/a>\u00a0|\u00a0 <a href=\"https:\/\/courses.bowdoin.edu\/computer-science-2200\/wp-content\/uploads\/sites\/106\/2015\/08\/ex-analysis2.pdf\">ex-analysis2<\/a><\/li>\n<li>Slides:\u00a0<a href=\"https:\/\/courses.bowdoin.edu\/computer-science-2200\/wp-content\/uploads\/sites\/106\/2015\/09\/01-cs2200-introduction.pdf\">S-intro.pdf<\/a>\u00a0|<a href=\"https:\/\/courses.bowdoin.edu\/computer-science-2200\/wp-content\/uploads\/sites\/106\/2015\/09\/02-cs2200-asymptotic-notation.pdf\">\u00a0S-asymptotic.pdf<\/a><\/li>\n<li><strong>Reading Assignment:<\/strong>\u00a0CLRS 1, 2, 3<\/li>\n<li><strong>Lab<\/strong>: <a href=\"https:\/\/courses.bowdoin.edu\/computer-science-2200\/wp-content\/uploads\/sites\/106\/2015\/09\/lab1.pdf\">Lab1<\/a>\u00a0(big-O)<\/li>\n<\/ul>\n<h2>Week 2<\/h2>\n<ul>\n<li><strong>Topic:<\/strong> Summations and recurrence relations. Mergesort.<br \/>\nNotes: <a href=\"https:\/\/courses.bowdoin.edu\/computer-science-2200\/wp-content\/uploads\/sites\/106\/2015\/08\/L-summations.pdf\">L-summations<\/a>\u00a0| <a href=\"https:\/\/courses.bowdoin.edu\/computer-science-2200\/wp-content\/uploads\/sites\/106\/2015\/08\/ex-sum.pdf\">ex-sum<\/a>\u00a0| <a href=\"https:\/\/courses.bowdoin.edu\/computer-science-2200\/wp-content\/uploads\/sites\/106\/2015\/08\/L-recurrences.pdf\">L-recurrences<\/a>\u00a0| <a href=\"https:\/\/courses.bowdoin.edu\/computer-science-2200\/wp-content\/uploads\/sites\/106\/2015\/08\/ex-rec1.pdf\">ex-rec1<\/a>\u00a0| <a href=\"https:\/\/courses.bowdoin.edu\/computer-science-2200\/wp-content\/uploads\/sites\/106\/2015\/08\/ex-rec2.pdf\">ex-rec2<\/a>\u00a0| <a href=\"https:\/\/courses.bowdoin.edu\/computer-science-2200\/wp-content\/uploads\/sites\/106\/2015\/08\/ex-rec3.pdf\">ex-rec3<\/a>\u00a0|\u00a0<a href=\"https:\/\/courses.bowdoin.edu\/computer-science-2200\/wp-content\/uploads\/sites\/106\/2015\/08\/ex-rec4.pdf\">ex-rec4<\/a>\u00a0| <a href=\"https:\/\/courses.bowdoin.edu\/computer-science-2200\/wp-content\/uploads\/sites\/106\/2015\/09\/ex-rec1-sol.pdf\">ex-rec1-sol<\/a><\/li>\n<li><strong>Reading Assignment:<\/strong> CLRS A, 2.3, 4.4<\/li>\n<li><strong>Lab<\/strong>: <a href=\"https:\/\/courses.bowdoin.edu\/computer-science-2200\/wp-content\/uploads\/sites\/106\/2015\/09\/lab2.pdf\">Lab2<\/a>\u00a0(recurrences)<\/li>\n<\/ul>\n<h2>Week 3<\/h2>\n<ul>\n<li><strong>Topic:<\/strong>\u00a0 More recurrences. \u00a0Heaps and heapsort.<br \/>\nNotes: <a href=\"https:\/\/courses.bowdoin.edu\/computer-science-2200\/wp-content\/uploads\/sites\/106\/2015\/08\/L-heaps.pdf\">L-heaps<\/a>\u00a0|\u00a0<a href=\"https:\/\/courses.bowdoin.edu\/computer-science-2200\/wp-content\/uploads\/sites\/106\/2015\/08\/ex-heaps.pdf\">ex-heaps<\/a><\/li>\n<li><strong>Slides:<\/strong> <a href=\"https:\/\/courses.bowdoin.edu\/computer-science-2200\/wp-content\/uploads\/sites\/106\/2015\/09\/03-cs2200-heapsort.pdf\">S-heaps.pdf<\/a><\/li>\n<li><strong>Reading Assignment:<\/strong> CLRS 6<\/li>\n<li><strong>Lab<\/strong>:\u00a0 <a href=\"https:\/\/courses.bowdoin.edu\/computer-science-2200\/wp-content\/uploads\/sites\/106\/2015\/09\/lab3.pdf\">Lab3<\/a>\u00a0(heaps)<\/li>\n<\/ul>\n<h2>Week 4<\/h2>\n<ul>\n<li><strong>Topic:<\/strong> Quicksort.<br \/>\nSorting lower bound and sorting in linear time.<br \/>\nNotes:<a href=\"https:\/\/courses.bowdoin.edu\/computer-science-2200\/wp-content\/uploads\/sites\/106\/2015\/09\/L-quicksort.pdf\"> L-quicksort<\/a>\u00a0| <a href=\"https:\/\/courses.bowdoin.edu\/computer-science-2200\/wp-content\/uploads\/sites\/106\/2015\/09\/ex-quicksort.pdf\">ex-quicksort<\/a> | <a href=\"https:\/\/courses.bowdoin.edu\/computer-science-2200\/wp-content\/uploads\/sites\/106\/2015\/08\/L-sortlb.pdf\">L-sortlb<\/a>\u00a0| <a href=\"https:\/\/courses.bowdoin.edu\/computer-science-2200\/wp-content\/uploads\/sites\/106\/2015\/08\/ex-linearsort.pdf\">ex-linearsort<\/a>\u00a0|\u00a0<a href=\"https:\/\/courses.bowdoin.edu\/computer-science-2200\/wp-content\/uploads\/sites\/106\/2015\/08\/L-linsort.pdf\">L-linsort<\/a><\/li>\n<li><strong>Reading Assignment:<\/strong> CLRS 7, 8<\/li>\n<li><strong>Lab<\/strong>:\u00a0 <a href=\"https:\/\/courses.bowdoin.edu\/computer-science-2200\/wp-content\/uploads\/sites\/106\/2015\/08\/lab-4-computer-science-2200.pdf\">Lab4<\/a>\u00a0(quicksort)<\/li>\n<\/ul>\n<h2>Week 5<\/h2>\n<ul>\n<li><strong>Topic:<\/strong> Selection.\u00a0Divide-and-conquer algorithms (Strassen, maximum sub-array)<br \/>\nNotes: <a href=\"https:\/\/courses.bowdoin.edu\/computer-science-2200\/wp-content\/uploads\/sites\/106\/2015\/08\/L-selection.pdf\">L-selection<\/a>|\u00a0<a href=\"https:\/\/courses.bowdoin.edu\/computer-science-2200\/wp-content\/uploads\/sites\/106\/2015\/08\/ex-selection.pdf\">ex-selection<\/a>\u00a0|\u00a0\u00a0<a href=\"https:\/\/courses.bowdoin.edu\/computer-science-2200\/wp-content\/uploads\/sites\/106\/2015\/08\/L-divideandconquer.pdf\">L-divideandconquer<\/a>|\u00a0<a href=\"https:\/\/courses.bowdoin.edu\/computer-science-2200\/wp-content\/uploads\/sites\/106\/2015\/08\/ex-maxps.pdf\">ex-maxps<\/a><\/li>\n<li><strong>Reading Assignment:<\/strong> CLRS 9,\u00a04.1, 4.2<\/li>\n<li><strong>Lab<\/strong>:\u00a0<a href=\"https:\/\/courses.bowdoin.edu\/computer-science-2200\/wp-content\/uploads\/sites\/106\/2015\/08\/lab-5-computer-science-2200.pdf\">Lab5<\/a>\u00a0(selection)<\/li>\n<\/ul>\n<h2>Week 6<\/h2>\n<ul>\n<li><strong>Topic:<\/strong> Dynamic programming.<br \/>\nNotes: <a href=\"https:\/\/courses.bowdoin.edu\/computer-science-2200\/wp-content\/uploads\/sites\/106\/2015\/08\/L-dynprogr.pdf\">L-dynprogr<\/a>\u00a0|\u00a0<a href=\"https:\/\/courses.bowdoin.edu\/computer-science-2200\/wp-content\/uploads\/sites\/106\/2015\/08\/ex-rod.pdf\">ex-rod<\/a><\/li>\n<li><strong>Reading Assignment:<\/strong> CLRS 15.1<\/li>\n<li><strong>Lab<\/strong>:\u00a0 <a href=\"https:\/\/courses.bowdoin.edu\/computer-science-2200\/wp-content\/uploads\/sites\/106\/2015\/08\/lab-6-computer-science-2200.pdf\">Lab6<\/a>\u00a0 (dynamic programming)<\/li>\n<\/ul>\n<h2>Week 7<\/h2>\n<ul>\n<li><strong>Topic:<\/strong> Dynamic programming and greedy algorithms.<br \/>\nNotes: <a href=\"https:\/\/courses.bowdoin.edu\/computer-science-2200\/wp-content\/uploads\/sites\/106\/2015\/08\/L-LCS.pdf\">L-LCS<\/a>\u00a0| <a href=\"https:\/\/courses.bowdoin.edu\/computer-science-2200\/wp-content\/uploads\/sites\/106\/2015\/08\/L-weightedinterval.pdf\">L-weightedinterval<\/a>\u00a0|\u00a0<a href=\"https:\/\/courses.bowdoin.edu\/computer-science-2200\/wp-content\/uploads\/sites\/106\/2015\/08\/L-greedy.pdf\">L-greedy<\/a><\/li>\n<li><strong>Reading Assignment:<\/strong> CLRS 15.4, 16.1, 16.2<\/li>\n<li><strong>Lab<\/strong>: <a href=\"https:\/\/courses.bowdoin.edu\/computer-science-2200\/wp-content\/uploads\/sites\/106\/2015\/08\/lab-7-computer-science-2200.pdf\">Lab7<\/a>\u00a0(more dynamic programming and greedy)<\/li>\n<\/ul>\n<h2>Week 8<\/h2>\n<ul>\n<li><strong>Topic:<\/strong> Graphs: BFS, DFS.<br \/>\nNotes: <a href=\"https:\/\/courses.bowdoin.edu\/computer-science-2200\/wp-content\/uploads\/sites\/106\/2015\/08\/L-graphbasics.pdf\">L-graphbasics<\/a>\u00a0| <a href=\"https:\/\/courses.bowdoin.edu\/computer-science-2200\/wp-content\/uploads\/sites\/106\/2015\/08\/L-bfsdfs.pdf\">L-bfsdfs<\/a>\u00a0| <a href=\"https:\/\/courses.bowdoin.edu\/computer-science-2200\/wp-content\/uploads\/sites\/106\/2015\/08\/L-basicproblems.pdf\">L-basicproblems<\/a>\u00a0|\u00a0<a href=\"https:\/\/courses.bowdoin.edu\/computer-science-2200\/wp-content\/uploads\/sites\/106\/2015\/08\/L-kevinbacon.pdf\">L-kevinbacon<\/a><\/li>\n<li><strong>Reading Assignment:<\/strong> CLRS 22.1 &#8211; 22.3<br \/>\nInternet: Lecture slides by Kevin Wayne:\u00a0<a href=\"http:\/\/www.cs.princeton.edu\/~wayne\/kleinberg-tardos\/pdf\/03Graphs.pdf\" target=\"_blank\">graphs-basics<\/a>\u00a0(source:\u00a0http:\/\/www.cs.princeton.edu\/~wayne\/kleinberg-tardos\/pdf\/03Graphs.pdf)<\/li>\n<li><strong>Lab<\/strong>:\u00a0 <a href=\"https:\/\/courses.bowdoin.edu\/computer-science-2200\/wp-content\/uploads\/sites\/106\/2015\/08\/lab-8-computer-science-2200.pdf\">Lab8<\/a>\u00a0(graphs)<\/li>\n<\/ul>\n<h2>Week 9<\/h2>\n<ul>\n<li><strong>Topic:<\/strong> Graphs: Topological sort. Strongly connected components.<br \/>\nNotes: <a href=\"https:\/\/courses.bowdoin.edu\/computer-science-2200\/wp-content\/uploads\/sites\/106\/2015\/08\/L-topsort.pdf\">L-topsort<\/a>\u00a0|\u00a0<a href=\"https:\/\/courses.bowdoin.edu\/computer-science-2200\/wp-content\/uploads\/sites\/106\/2015\/08\/L-scc.pdf\">L-scc<\/a><\/li>\n<li><strong>Reading Assignment:<\/strong> CLRS 22.4, 22.5<\/li>\n<li><strong>Lab<\/strong>:\u00a0 <a href=\"https:\/\/courses.bowdoin.edu\/computer-science-2200\/wp-content\/uploads\/sites\/106\/2015\/08\/lab-9-computer-science-2200.pdf\">Lab9<\/a>\u00a0(graphs)<\/li>\n<\/ul>\n<h2>Week 10<\/h2>\n<ul>\n<li><strong>Topic:<\/strong> Graphs: Minimum spanning tree (Kruskal and Prim&#8217;s algorithms). Union-find structure.<br \/>\nNotes:\u00a0<a href=\"https:\/\/courses.bowdoin.edu\/computer-science-2200\/wp-content\/uploads\/sites\/106\/2015\/08\/L-mst.pdf\">L-mst<\/a><\/li>\n<li><strong>Reading Assignment:<\/strong> CLRS 23<br \/>\nInternet: Lecture slides <a href=\"http:\/\/www.cs.princeton.edu\/~wayne\/kleinberg-tardos\/pdf\/04GreedyAlgorithmsII.pdf\">greedy-algorithms<\/a>\u00a0(source:http:\/\/www.cs.princeton.edu\/~wayne\/kleinberg-tardos\/pdf\/04GreedyAlgorithmsII.pdf)\u00a0| Kruskal demo <a href=\"http:\/\/www.cs.princeton.edu\/~wayne\/kleinberg-tardos\/pdf\/04DemoKruskal.pdf\" target=\"_blank\">demo-kruskal<\/a>\u00a0(source:\u00a0http:\/\/www.cs.princeton.edu\/~wayne\/kleinberg-tardos\/pdf\/04DemoKruskal.pdf)\u00a0| Prim demo <a href=\"http:\/\/www.cs.princeton.edu\/~wayne\/kleinberg-tardos\/pdf\/04DemoPrim.pdf\" target=\"_blank\">demo-prim<\/a>\u00a0(source:\u00a0http:\/\/www.cs.princeton.edu\/~wayne\/kleinberg-tardos\/pdf\/04DemoPrim.pdf)\u00a0by Kevin Wayne.<\/li>\n<li><strong>Lab<\/strong>:\u00a0 <a href=\"https:\/\/courses.bowdoin.edu\/computer-science-2200\/wp-content\/uploads\/sites\/106\/2015\/08\/lab-10-computer-science-2200.pdf\">Lab10<\/a>\u00a0(graphs)<\/li>\n<\/ul>\n<h2>Week 11<\/h2>\n<ul>\n<li><strong>Topic:<\/strong> Graphs: Single-source shortest paths (Bellman-Ford and Dijkstra&#8217;s algorithms).<br \/>\nNotes:\u00a0<a href=\"https:\/\/courses.bowdoin.edu\/computer-science-2200\/wp-content\/uploads\/sites\/106\/2015\/08\/L-shpaths.pdf\">L-shpaths<\/a><\/li>\n<li><strong>Reading Assignment:<\/strong> \u00a0CLRS 24.1-24.3<br \/>\nDijkstra demo by Kevin Wayne\u00a0<a href=\"http:\/\/www.cs.princeton.edu\/~wayne\/kleinberg-tardos\/pdf\/04DemoDijkstra.pdf\">demo-dijkstra<\/a>\u00a0(source:\u00a0http:\/\/www.cs.princeton.edu\/~wayne\/kleinberg-tardos\/pdf\/04DemoDijkstra.pdf)<\/li>\n<li><strong>Lab<\/strong>:\u00a0 <a href=\"https:\/\/courses.bowdoin.edu\/computer-science-2200\/wp-content\/uploads\/sites\/106\/2015\/08\/lab-11-computer-science-2200.pdf\">Lab11<\/a>\u00a0(graphs)<\/li>\n<\/ul>\n<h2>Week 12<\/h2>\n<ul>\n<li><strong>Topic:<\/strong> Last class: Crash course into NP-completeness.<br \/>\nQuestions from technical interviews.<\/li>\n<li><strong>Reading Assignment:<\/strong> (CLRS 34)<br \/>\nInternet: Lecture slides by Kevin Wayne\u00a0<a href=\"http:\/\/www.cs.princeton.edu\/~wayne\/kleinberg-tardos\/pdf\/08IntractabilityI.pdf\">intractability<\/a>\u00a0(source:\u00a0http:\/\/www.cs.princeton.edu\/~wayne\/kleinberg-tardos\/pdf\/08IntractabilityI.pdf)<\/li>\n<\/ul>\n<p><em>Exam 2 will be in-class, \u00a0on (check final exam date in polaris).<\/em><\/p>\n","protected":false},"excerpt":{"rendered":"<p>This schedule is tentative, and will be updated as the semester progresses. Week 1 Topic: Class intro. Warmup with searching (linear and binary) and sorting (bubble sort, insertion sort, selection sort).\u00a0Analysis: The RAM model. Asymptotic analysis and asymptotic notation. Case studies. Notes: L-intro\u00a0| ex-bubblesort\u00a0|\u00a0 ex-selsort\u00a0|\u00a0 L-analysis\u00a0| ex-inssort\u00a0| ex-analysis1\u00a0|\u00a0 ex-analysis2 Slides:\u00a0S-intro.pdf\u00a0|\u00a0S-asymptotic.pdf Reading Assignment:\u00a0CLRS 1, 2, 3 [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-43","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/courses.bowdoin.edu\/computer-science-2200\/wp-json\/wp\/v2\/pages\/43","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/courses.bowdoin.edu\/computer-science-2200\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/courses.bowdoin.edu\/computer-science-2200\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/courses.bowdoin.edu\/computer-science-2200\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/courses.bowdoin.edu\/computer-science-2200\/wp-json\/wp\/v2\/comments?post=43"}],"version-history":[{"count":0,"href":"https:\/\/courses.bowdoin.edu\/computer-science-2200\/wp-json\/wp\/v2\/pages\/43\/revisions"}],"wp:attachment":[{"href":"https:\/\/courses.bowdoin.edu\/computer-science-2200\/wp-json\/wp\/v2\/media?parent=43"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}