Introduction to Data Structures and Algorithms

SPRING 2024

=============================================================

 

CSE101 Introduction to Data Structures and Algorithms

Course Staff:

  • Instructor: Prof. Davis (davisje@ucsc.edu)
    • Office hours: (immediately after class I take questions until there are no more)

  • Graduate TAs
    • Eren Dogan                (erdogan@ucsc.edu)
    • Minghao Liu               (mliu40@ucsc.edu)
    • Marzia Binta Nizam   (manizam@ucsc.edu)
    • Vanshika Vats             (vvats@ucsc.edu)

  • Undergraduate Tutors
 

Lab Sections:

Section Day Time TA/Tutor Location
Section 1 Monday 08:00 - 09:05 Minghao/Joost E2-192
Section 6 Monday 19:10 - 20:15 Minghao Zoom, E2-192
Section 2 Wednesday 13:20 - 14:25 Vanshika/Alyssa E2-192
Section 3 Wednesday 17:20 - 18:25 Marzia/Jinsung E2-194
Section 4 Friday 10:40 - 11:45 Eren/Chloe E2-194
Section 5 Friday 16:00 - 17:05 Githika/Riya Crown 208

 

Office Hours:

Please also check Piazza for any sudden schedule changes!

Monday Tuesday Wednesday Thursday Friday
Lab Section: Minghao/Joost
8:00 am - 9:05 am
E2-192

Office Hours:
Riya Narang
7:30 - 9:30 am
McHenry 4th Floor 4362
Office Hours:
Riya Narang
9:00 - 11:00 am
McHenry 4th Floor 4362

LSS Session:
Alexander
9:50 - 10:50 am

TutorHub Signup
ARCenter Rm 202

Office Hours:
Eren Dogan
10:00 - 11:00 am Zoom

 Lab Section: 
Eren/Chloe
10:40 - 11:45 am
E2-194
Office Hours:
Joost "Will" 
11:30 am - 1:30 pm
Zoom		 Office Hours:
Githika
12:00 - 2:00 pm
McHenry 2nd Floor Room 2353
Office Hours:
Jinsung
1:30 - 3:00 pm
Zoom		 Lab Section:
Vanshika/Alyssa
1:20 - 2:25 pm
E2-192		 Office Hours:
Vanshika
12:00 - 1:00 pm
Zoom		 Office Hours:
Joost "Will" 
1:00 - 3:00 pm
Zoom

LSS Session:
Alexander
4:00 - 5:00 pm

TutorHub Signup
Oakes LC #4

 Office Hours:
Alyssa
3:20 - 4:55 pm
Porter Acad 241		 Office Hours:
Marzia
4:00 - 5:00 pm
Zoom		 Office Hours:
Jinsung
1:30 - 3:00 pm
Zoom

Lab Section: 
Githika/Riya
4:00 - 5:05 pm
Crown 208
Lab Section:
Minghao Liu
7:10 - 8:15 pm
Zoom

Lecture: 
5:20 - 6:55 pm
E&MB206

 Lab Section:
Marzia/Jinsung
5:20 - 6:25 pm
E2-194		 Lecture: 
5:20 - 6:55 pm
E&MB206

LSS Session:
Alexander
7:10 - 8:10 pm

TutorHub Signup
ARCenter Rm 116

 Office Hours:
Alyssa
7:10 - 8:45 pm
Porter Acad 249
Office Hours:
Chloe
8:00 - 10:00 pm
Zoom
Links to an external site.		 Office Hours:
Chloe
8:00 - 10:00 pm
Zoom

 

Piazza:

FAQ:

  • Is there a section during the first week of classes?
    • NO
  • Do I have to come?
    • This is an in-person class.  Tests are in person. You have to be there for those. There may be graded classroom activities, bummer for you if you miss. I will not explicitly take attendance.
  • What about the discussion sections, do I have to go to those?
    • Yes you must reserve this time in your schedule. In past versions of this class tests were in discussion time. We are attempting to move those to class time. If we succeed then discussion is optional, if we fail and have to move tests back to discussion, you will need to be there. Keep it reserved in your schedule.
  • Do I have to buy the book?
    • The book is "optional". Although its an excellent book that will serve you well. We will use codio for assignments and exams, and you do need to pay for that service if you stay in the course beyond week 3.
  • This is also offered by another instructor. Is it the same?
    • As similar as we can manage, but I expect many details will be different. 
  • Can I have a permission code?
    • Instructors do not have permission codes. This was a policy change. Its useless to email me. You have to wait until waitlist is active and get on that. If you have weird prereq issues I think your only hope is the advising office.
  • I have other special cases I need to ask about.
    • If it can wait until we get class started please wait. 90% of questions repeat and are not immediately actionable.

Course Textbooks

Lectures

Lecture Schedule:

Date Topics HWs Tests Slides Handout Reference
Week 1 4/2 Introduction - -

Intro
4/4 Linked lists Lecture 2
Week 2 4/9 Linked lists continued - Lecture 3
4/11 Stacks, recursion through stacks Lecture 4
Week 3 4/16 Recursion to generate all substrings, Asymptotic analysis, Big-Oh notation HW1
Due April 21 - Noon		 Linked list
April 18		 Lecture 5   Chap 3, CLRS
4/18 linear time, constant time, analysis of simple sorting algorithms Lecture 6 Chap 3, CLRS
Week 4 4/23 Binary search analysis, starting binary heaps - - Lecture 7 Heap viz by Melezinek Chap 6, CLRS
4/25 Binary heaps Lecture 8 Chap 6, CLRS
Week 5 4/30 BSTs continued

HW2

Due May 5 - Noon

 Stacks
May 2		 Lecture 9  BST viz by Melezinek Chap 12, CLRS
5/2 Tree traversals, self-balancing BSTs Lecture 10 Chap 12, 13 CLRS, wikipedia
Week 6 5/7 AVL trees - - Lecture 11 AVL viz by Galles Chap 12, 13 CLRS
5/9 Hash tables Lecture 12 Chap 11, CLRS
Week 7 5/14 Merge sort and quicksort HW3
Due May 19 - Noon		 Heaps/Trees
May 16		 Lecture 13   Chap 2.3, 4, 7, CLRS 
5/16 Solving algorithms problems – I Lecture 14  
Week 8 5/21 Solving algorithms problems - II - - Lecture 15
5/23 Graphs and BFS Lecture 16 Chap 22, CLRS
Week 9 5/28

Loop invariants and proving BFS correctness

 HW4
Due June 2 - Noon		 Arrays and simple data structures
May 30		 Lecture 17   Chap 2, 22, CLRS
5/30

Single-source shortest path algorithms

 Lecture 18 Chap 24, CLRS
Week 10 6/4

DFS

 - - Lecture 19 Chap 22, CLRS
6/6

??
Finals Week 6/11 - - Graphs
June 13		      
6/13 -

What we did in classtime:

  • 4/1
    • Intro class
  • 4/4 
    • Practice problems - linked lists
    • Discuss political ChatGPT
  • 4/9
    • Practice problems - linked lists
    • About the professor
  • 4/11
    • Cancelled - Power out on campus
  • 4/16
    • Practice test in codio
  • 4/18
    • Real test in codio
  • 4/23
    • Palindrome discussion, Substring practice problem, Generative AI on ethnicity
  • 4/25
    • Jobs and grad school lecture
  • 4/30
  • 5/2
    • Test on Stacks
  • 5/7
    • BST - Insert, Delete; Social Issues:Facts!
  • 5/9
    • BST - LCA, Width; 2D Sorting - BSP Trees

Grading

  • Tests
    • There are 5 of them (3 in Codio where you code, 2 in Canvas written style)
    • These determine whether you pass the class or not
    • Details:
      • You get a set of questions in advance, on test day you get one of them
      • ~20 lines of code
      • Drop the worst test 
        • e.g. 5/10, 10/10, 7/10, 5/10, 10/10 = (5+10+7+10)/40=80%
      • score 70% or above and you insure at least a C
      • score 90% or above and you insure at least a B-
  • HW
    • There are 4 of them
    • These control A,B,C grade
    • Details:
      • ~ 100s of lines of code
      • Your code will be run against test cases, strict and tough
      • Drop the worst HW
      • score 50%, you get at least B-
      • score 80%, you get at least A-

Homework

You complete this in codio. This is a paid service (you can get a refund if you drop the class). It provides a virtual machine in a web page, so that we all have the same programming environment. Instructions to sign up for codio can be found at Codio Set Up. The details of these assignments will be in the codio system. 

  • Due Week 3 - Linked Lists
  • Due Week 5 - Recursion and stacks
  • Due Week 7 - Trees
  • Due Week 9 - Graphs

Exams

Some exams are also in codio with code answer, and some exams are in canvas with written answers. For exams 1,2,3 in codio, you write real code which must work. Example study questions which closely match the exams will be provided. For exams 4,5 you write psuedocode, the sample questions will be released in the Files section of Canvas, and you take the exam in Canvas.  For all exams, you open a full screen window and do your work there. You may not switch tabs or reference other digital content. Notes are not allowed in the exam. You will need to bring a laptop to take the exams.