Syllabus (Spring 2023)

Catalog Number 56:198:501 (also cross-listed as 56:121:531)
Instructor Sunil Shende
Schedule Synchronous Online on Tuesdays from 6 pm to 8:40 pm (in-person in BSB 334)
Office Hours Zoom meetings weekly on Mondays from 11:20 am to 12:20 pm (free period), and 6 pm to 7:30 pm
Email shende AT camden DOT rutgers DOT edu
Textbook Algorithms Illuminated, by Dr. Tim Roughgarden; Soundlikeyourself Publishing (2018)

The main goal of this graduate course is to expose students to many common data structures like arrays, linked lists tree structures and hash tables, and to fundamental techniques for algorithm design and analysis. A variety of application contexts will be considered. We will use the Python programming language along with specific frameworks and libraries from the Python ecosystem to implement algorithms and data structures.

Note: The course emphasizes implementation details, algorithm correctness and computational efficiency. It is a hands-on course! Students who are unfamiliar or rusty with Python coding must be prepared to quickly get up to speed with the language constructs, object-oriented programming and built-in modules by the end of the first two weeks.

Learning Outcomes

Students will master:

  • basic skills for analyzing efficient data structures and algorithms
  • programming tools and libraries for developing literate (i.e., self-documented, reproducible) programs and algorithms in Python
  • algorithmic problem-solving including the use of specific techniques for algorithm design like divide-and-conquer, greedy strategies and dynamic programming

Logistics

This course is cross-listed in the CCIB Ph.D program and the Applied Computing MBS program. We will be using the Rutgers Canvas site for the course as the focal point for sharing all class material.

The class will meet in a synchronous, online format: attendance during class sessions is mandatory, especially since the class will run in a flipped mode. In brief:

  • All “lectures” will be available either as short videos pre-recorded by me, or videos from Dr. Roughgarden’s video playlists based on the textbook.
  • Students are expected to watch the video lectures and read any additional assigned material in sequence (as posted in the Canvas modules), in advance of the Tuesday class sessions.
  • You should ideally buy the textbook as well to read the corresponding listed sections – the book is available either in separate parts (we will cover material from the first three parts out of four) or as an “omnibus” volume.
  • The class sessions on Tuesdays will consist of a review and clarifications of salient parts from that week’s readings/videos, and short in-class assessments (such as quizzes, written exercises, and programming exercises). In addition, students will start working on longer “homework” problems that should be completed and submitted by Saturday that week. A document explaining the typical weekly “schedule” of activities in a class session will be posted separately under the Canvas module for Week 1.
  • Approximately every alternate weekend, students will work on a longer, online assessment that tests their understanding and mastery of material covered in the previous two or three weeks. The technical nature of the material entails that the assessments will inevitably require some amount of cumulative knowledge accrued over the semester.
  • There will be no midterm or final exams in the course.
  • Class discussions will be facilitated through the Canvas site for the course; participation in the discussions is mandatory and will be part of the grade.
  • Students must check-in during one of the office hour sessions at least once in two weeks.

Tentative Schedule of Topics

Please bookmark the Algorithms Unlimited textbook website to select and watch individual videos. Where necessary, I will provide alternative references, notes and video clips.

Week Topics Textbook Sections Weekend Assessment
1 Arrays; Linked lists; Stacks & Queues    
2 Recursion; Binary Trees; Mergesort Appendix A; Sec. 1.1 – 1.6 Test 1
3 Asymptotic Notation Sec. 2.1 – 2.5  
4 Divide and Conquer Sec. 3.1 – 3.3 Test 2
5 Master Theorem; Quicksort Sec. 4.1 – 4.3; Sec. 5.1 – 5.3  
6 Random Quicksort; Hashing Appendix B; Sec. 5.4 – 5.5; Sec. 12.1 – 12.4 Test 3
7 Heaps Sec. 10.1 – 10.3; 10.5  
  Spring Break    
8 Search Trees; Treaps Sec. 11.1 – 11.3 Test 4
9 Graphs; Breadth-First Search Sec. 7; Sec. 8.1 – 8.3  
10 Depth-First Search Sec. 8.4 – 8.6 Test 5
11 Dijkstra’s Shortest-Path Algorithm Sec. 9; Sec. 10.4  
12 Minimum Spanning Trees Sec. 15 (except 15.6) Test 6
13 Dynamic Programming Sec. 16.1 – 16.4  
14 Dynamic Programming Sec. 16.5; Sec. 17.1 Test 7

Additional Resources

There are lots of supplemental textbooks on algorithms and data structures;
among them, the following are recommended for additional reading and practice:

  • Problem Solving with Algorithms and Data Structures using Python, 2nd. edition by Miller & Ranum; published by Franklin, Beedle and Associates Inc. (2011).

  • Algorithms Unplugged, by Thomas Cormen; The MIT Press (2013).

  • Algorithms by Dasgupta, Papadimitriou and Vazirani; McGraw-Hill Education (2006).

  • Introduction to Algorithms (3rd edition) by Cormen, Leiserson, Rivest and Stein; The MIT Press (2009).

For additional videos, MIT’s 6.006 Course (Fall 2011) playlist is based on the textbook by Cormen et al. listed above.

Course Grade

The overall grade will be apportioned as follows:

  • 35% Weekend Tests (omit worst grade out of 7)
  • 30% Homework (omit worst 2 grades)
  • 30% Weekly In-Class Assessments (omit worst 2 grades)
  • 5% Discussion participation

Since I will be dropping the worst grades for each category of assessment (other than Discussions), there will be no makeup opportunities. Late submission of homework problem sets will generally not be entertained except in the case of a verifiable, documented emergency (medical or personal). If there are medical reasons for requiring special accommodation, e.g., extra time on the in-class or weekend assessments, please obtain the relevant documents from the Division of Student Affairs.

Letter grade rubric

I generally use (with some minor variation at my discretion) the following rubric:

  • an A grade for overall points above 85%
  • a B+ grade in the range 75 – 85%
  • a B grade in the range 65 – 75%
  • a C+ grade in the range 60 – 65%
  • a C grade in the range 50 – 60%

Anything below 50% is considered unsatisfactory (either a D or F grade).

Academic Integrity

Student collaboration and online discussions on Canvas are certainly encouraged. However, unless noted otherwise, any required submission that will be graded (quizzes, homework, exams) and any other normative assessment must be completed individually without any external assistance (that specifically means not using someone outside class to do your work, or obtaining solutions from the internet, a book or someone else in class). “Copying” from someone else especially without citation or allowing your work to be copied by others constitutes cheating, as does plagiarism from sources including books and the web.

Any violations of academic integrity will be dealt with immediately and severely as per the Rutgers Academic Integrity Policy and Student Code of Conduct. Please read and understand the policy carefully!