Data Structures and Algorithms (NYU Paris, Spring 2021)
The design and analysis of efficient data structures is a vital subject in computing and is part of the curriculum of every computer science and computer engineering student. In this course, we will learn how to model computational problems. We will cover the most important algorithms, algorithmic paradigms and data structures used to solve those problems. We will discuss efficiency and scalability.
More specifically, the course will cover topics such as object oriented programming, as well as Sorting and Trees, Hashing, Number theoretic algorithms including RSA encryption, Graphs and Shortest paths and the notion of NPCompleteness.
The students will get the opportunity to program the algorithms that are discussed during the lectures in Java.
The class will follow the structure
1. Lectures (introduction of the new material that will be needed during the lab sessions and for the assignments)
2. Programming (lab) sessions, (you have the opportunity to apply what you have learned during the lecture, and you can ask all the questions you want to make sure you understand everything before the assignement)
3. Assignments (You are given a new problem and you are evaluated on your ability to use the course material to solve this new problem)
Schedule and Classroom
Lecture: Tuesday/Thursday, 12.30pm – 1.45pm (Paris time), Room 410
Recitations: Tuesday 2.15pm – 3.45pm (Paris time). Room 410
Office hour: Thursday 2.15pm – 3.45pm (Paris time)
Assignments policy
Except if explicitely stated otherwise, assignments are due at the beginning of each class.
Current (temporary) version of the notes: Lecture notes
Practice (theory) Questions for each exam can be found by clicking on those exams below
Exam : 60% of the grade (30% midterm, 30% final)
Assignments : 30 % of the grade (Tentative schedule below)
Final Project : 10 % of the grade (Tentative schedule below)
The Github page for the class will be hosted at https://github.com/acosse/DataStructures2021 and will be used for the lab and the assignments. You can also click on each “Lab” in the schedule below and this will redirect you to the github page.
Tentative schedule:
Legend: Lab sessions are in green, Homeworks are in red (right side of the table), dates related to the project are in orange.
Week #  date  Topic  Assignements 
Week 1  01/26, 01/28  Reminders/Intro to Java, Elementary programming
including loops, strings, arrays, objects, classes,… Lab 1 (Setting up Java, git,..) Slides 

Week 2  02/02, 02/04  Object Oriented Programming and Design, Part I,
Lab 2
Slides, Solution Ex1.1., Solution Ex1.2., Solution Ex1.3. 
Assign. 1 
Week 3  02/09, 02/11 
Object Oriented Programming and Design Part II including inheritance and Abstract classes, Lab 3 Slides Inheritance, Slides arrays , Solutions Exercise 1.1 and 1.3 
Assign. 1 due, 
Week 4  02/16, 02/18  Fundamental data structures
Multidimensional arrays, Linked Lists, Numerics, integers, RSA encryption, Slides, Lab 4 Solution Ex. 1.1, Ex. 1.7 (with Object) 
Assignment 2 
Week 5  02/23, 02/25  Algorithm analysis including Asymptotic Analysis and the “Big Oh” notation Slides  Assign.2 due 
Week 6  03/02, 03/04  Recursion,
Slides, Lab 5, Solutions exercises 1.1, 1.4 and 1.10


Week 7  03/09, 03/11  Stacks, Queues and Deques
(Possibly List ADT),
Slides
Lab 6


Week 8  03/16, 03/18  Trees Part I including general and Binary Trees, Tree Traversal algorithms,.. Slides Part I , Slides Part II, Lab 7, Solutions 

Week 9  03/23, 03/25  Trees Part II (including Search Trees, Balanced Search Trees)
Slides 1, Slides 2 , Slides 3, Lab 8 

Week 10  03/30, 04/01  Priority queues, Heaps, Maps, Hash Tables
Slides Priority Queues,
Slides Maps,
Slides Hash Table (Part II), Lab 10 

Week 11  04/06, 04/08  Sorting Part I, Lab 11  
Week 12  04/13, 04/15  Sorting part II, Lab 12  
Week 13  04/20, 04/22  Graph Algorithms including BFS, DFS, topological Sort, Min Spanning trees, Max Flow,.. Lab 13 
Assignment 3

Week 14  04/27, 04/29  Advanced Topics including Dynamic Programming, Linear Programming, Approximation and Randomized Algorithms,… 

Week 15  05/04, 05/06  Revisions (link to Lab) Element iterator demo, Position iterator demo
Tree demo 
 Data structures and algorithms in Java, Goodrich, Tamassia, Goldwasser
 A Java Reference: Assorted Java Reference Material, Paul N. Hilfinger, UCB
 The Java Language Specification (Java SE 14 Edition) by James Gosling, Bill Joy, Guy Steele, Gilad Bracha, Alex Buckley, and Daniel Smith
 Introduction to Java programming and data structures, Y. Daniel Liang.
 See also
Lab Sessions and programming policy
The lab sessions will require you to do some programming.
Downloading and getting started with Java.