#  CS120: Intro to Algorithms and their Limitations 

 





 Semester:   Fall 

|

 Year offered:  2021 

 

 

 

 An introductory course in theoretical computer science, aimed at giving students the power of using mathematical abstraction and rigorous proof to understand computation. Thus equipped, students will be able to design and use algorithms that apply to a wide variety of computational problems, with confidence about their correctness and efficiency, as well as recognize when a problem may have no algorithmic solution. At the same time, they will gain an appreciation for the beautiful mathematical theory of computation that is independent of (indeed, predates) the technology on which it is implemented.

###  Links

- [Syllabus](/file_url/432), [Content Plan](/file_url/431), and [Textbooks](/file_url/433)
- [Schedule, Lecture Notes, Assignments](/classes/cs120-intro-algorithms-and-their-limitations/materials/schedule-lecture-notes-and)
- [Ed](https://canvas.harvard.edu/courses/93367/external_tools/78506?display=borderless) (forum for discussions, announcements, Q&A, communication with course staff)
- [Gradescope](https://www.gradescope.com/courses/292947) (for submitting and receiving feedback on assignments)
- [Canvas](https://canvas.harvard.edu/courses/93367) (has lecture recordings - check both Panopto and Zoom cloud recordings)
- Participation Portfolio [Guidelines](/file_url/479) and [Examples](/file_url/478)
- [Q evaluation](/file_url/480)

---

## Class Materials:

### Schedule, Lecture Notes, and Assignments

Sort    Sort    **Date**

 





  **Title**

 





  **Reading**

 





  **Lecture Notes**

 





  **Assignments & Other Handouts**

 





    Aug 20

 





  Course overview

 





  





  [Zoom whiteboard](/file_url/420)

 





  draft [syllabus](/file_url/416), [ps0](/file_url/419), [content](/file_url/418), [textbooks](/file_url/417)

 





   ##  **1. Storing and Searching** 

 





  





  





  





    Sep 2

 





  Sorting; Computational Problems

 





  CS50 Week 3, Roughgarden I Sec. 1.4, 1.5, CLRS 1.3

 





  [pdf](/file_url/427) 





  





    Sep 7 





  Measuring Efficiency 





  Roughgarden I Ch. 2, CLRS Ch. 2 & Sec 8.1, Lewis-Zax Ch. 21 





  [pdf](/file_url/422) 





  [ps1](/file_url/425) 





    Sep 9 





  Data Structures 





  CS50 Week 5, Roughgarden II Sec 10.1 & 11.1, CLRS Ch. 10 





  [pdf](/file_url/426) 





  [activelearning1](/file_url/424) 





    Sep 14 





  Dynamic Data Structures 





  Roughgarden II Sec. 11.0-11.3.2 , CLRS Ch. 10, Sec. 12.0-12.1 





  [pdf](/file_url/429) 





  [ps2](/file_url/430) 





    Sep 16 





  Binary Search Trees 





  Roughgarden II Sec. 11.2-11.3.7, CLRS Sec. 12.0-12.3 





  [pdf](/file_url/428) 





  





    Sep 21 





  Balanced BSTs 





  Roughgarden II Sec. 11.4, CLRS Ex. 13-3 





  [pdf](/file_url/437) 





  [activelearning2](/file_url/466), [ps3](/file_url/476) 





    Sep 23 





  The RAM Model 





  





  [pdf](/file_url/442) 





  





    Sep 28 





  Randomized Algorithms: QuickSelect 





  Lewis-Zax Ch. 26-29, CLRS 9.0-9.2, Roughgarden I Sec. 6.0-6.2 





  [ pdf](/file_url/453) 





  [activelearning3](/file_url/463),  
[ps4](/file_url/477) 





    Sep 30 





  Randomized Data Structures: Hash Tables 





  CLRS Sec. 9.2, Roughgarden II Sec. 12.0-12.4 





  [pdf](/file_url/434) 





  





    Oct 5 





  Storing & Search Synthesis, Intro to Graph Search 





  CLRS Sec 11.3, Roughgarden II Sec 12.3.6-12.4, Roughgarden II Sec 7.1-7.2, CLRS Apdx B.4 





  [pdf](/file_url/438) 





  





   ##  **2. Graph Algorithms** 

 





  





  





  





    Oct 7 





  Graph Search 





  Roughgarden II Sec 8.1-8.2, CLRS Sec 12.2 





  [pdf](/file_url/436) 





  





    Oct 12 





  Graph Search (cont.) 





  Roughgarden II Sec 7.3-7.4, 8.2, CLRS Sec 22.0-22.2 





  [pdf](/file_url/441) 





  [activelearning4](/file_url/467),  
[ps5](/file_url/469) 





    Oct 14 





  Midterm 





  





  





  





    Oct 19 





  Graph Coloring 





  Lewis-Zax Ch. 18, Roughgarden III Sec 13.1 





  [pdf](/file_url/439) 





  [ps6](/file_url/470) 





    Oct 21 





  Independent Sets 





  CLRS Sec 16.1-6.2 





  [pdf](/file_url/435) 





  [activelearning5](/file_url/468) 





    Oct 26 





  Matchings 





  





  [pdf](/file_url/443) 





  [ps7](/file_url/471) 





    Oct 28 





  Graph Algorithms Synthesis, Ethics, Logic 





  Lewis-Zax, Ch 9-10 





  [pdf](/file_url/452) 





  





   ##  **3. Logic Algorithms** 

 





  





  





  





    Nov. 2 





  Satisfiability 





  Lewis-Zax Ch. 9-10, Roughgarden IV Sec 21.5, Ch. 24 





  [pdf](/file_url/440) 





  [ps8](/file_url/472) 





    Nov. 4 





  Resolution and SAT Solvers 





  





  [pdf](/file_url/444) 





  [activelearning6](/file_url/465) 





   ##   **4. Computability Theory** 

 





  





  





  





    Nov. 9 





  Program Analysis, Universal RAM Program, Halting Problem 





  MacCormick Sec 6.0-6.4, MacCormick Ch. 3, [SMT survey](https://dl.acm.org/doi/pdf/10.1145/1995376.1995394?download=true) 





  [pdf](/file_url/449) 





  [ps9](/file_url/474) 





    Nov. 11 





  Unsolvable Problems 





  MacCormick Ch. 7 





  [pdf](/file_url/450) 





  





    Nov. 16 





  The Church-Turing Thesis 





  MacCormick Sec 5.6-5.7, 7.7-7.9 





  [pdf](/file_url/446) 





  [activelearning7](/file_url/462) 





    Sort   ##   **5. Computational Complexity** 

 











  











  



 





  





  





  





    Nov. 18 





  Computational Complexity 





  MacCormick Sec 5.3-5.5, Ch. 10, 11 





  [pdf](/file_url/445) 





  





    Nov. 23 





  NP and NP-completeness 





  MacCormick Sec 12.0-12.3 





  [ pdf](/file_url/454) 





  [ps10](/file_url/475) 





    Nov. 30 





  NP-completeness 





  MacCormick Ch. 13, 14, 17 





  [pdf](/file_url/451) 





  





    Dec. 2 





  The P vs. NP Problem 





  MacCormick Sec 14.4, 14.6, 14.8 





  [pdf](/file_url/448) 





  [activelearning8](/file_url/464),  
[ps11](/file_url/473)​​​​​​​ 





    Dec. 7 





  Review, Synthesis, Conclusions 





  Roughgarden IV Epilogue, MacCormick, Ch. 18 





  [ pdf](/file_url/447) 





  





    Sort   ##