CSE250, Spring 2022

Data Structures

Instructor:

Dr. Kenneth W. Regan

326 Davis

645-4738

Office hours: Tue. 1--2:30pm; Wed. 2-3pm (definite), other times TBA

email

TAs: 1.

Mingxi Lei

302 Davis

no phone

Ofc. hrs.: TBA

email

2.

Yutian Yan

302 Davis

no phone

Ofc. hrs.: TBA

email

GTAs 3.

Praneeth Sai Kotha

302 Davis

no phone

Ofc. hrs.: TBA

email

4.

Vindhya Nuthalapati

302 Davis

no phone

Ofc. hrs.: TBA

email

UTAs 5.

Sarthak Agarwal

302 Davis

no phone

Ofc. hrs.: TBA

email

6.

Sean Grzenda

302 Davis

no phone

Ofc. hrs.: TBA

email

7.

Pantelis Kiamos

302 Davis

no phone

Ofc. hrs.: TBA

email

8.

Korey Liu

302 Davis

no phone

Ofc. hrs.: TBA

email

9.

Vrund Patel

302 Davis

no phone

Ofc. hrs.: TBA

email

10.

Romika Sairam

302 Davis

no phone

Ofc. hrs.: TBA

email


Lectures and Recitations (all in-person)

Recitations do not meet in Week 1. Note times are not in week order
(LEC)
MWF 1:00--1:50pm in Knox 110
(R1)
Mondays 3:00--3:50pm in Bell 340
(R2)
Wednesdays 5:00--5:50pm in Bell 340
(R3)
Mondays 5:00--5:50pm in Bell 340
(R4)
Wednesdays 3:00--3:50pm in Bell 340
(R5)
Mondays 10:00--10:50am in Bell 340
(R6)
Tuesdays 1:00--1:50pm in Bell 340
(R7)
Mondays 2:00--2:50pm in Bell 340

Examinations:

  • Two prelims, the first on Wednesday, March 9, in class period. The second will be in late April. (It has been fixed for Friday, April 29, in class period.)
  • One cumulative 3-hr. final.



Lecture Notes in 2021 (will appear here)

  1. Week 1: MWF
  2. Week 2: MWF
  3. Week 3 Lectures: Mon. Wed.-Mon. (lab notes)
  4. Week 4 Notes (Friday into week 5 Monday)
  5. Week 5 Wed. & Fri.
  6. Week 6 Mon.
  7. Week 7 Mon.
  8. Week 8 MW
  9. Week 9 MWF
  10. Week 10: MWFM (incl. Mon. 4/18)
  11. Week 11: WF
  12. Week 12: MW
  13. Week 13: MWF
  14. Week 14: MWF


Assignments (will appear here)

  1. Assignment 1, due 2/16 11:59pm
  2. Assignment 2, due 3/2 11:59pm (Keys to both below)
  3. Assignment 3 (50 pts.) has been posted on UBLearns and is due Tue. 3/8 (was extended to noon) Plain-text version with answers
  4. Assignment 4, due Sat. 4/9, 11:59pm
  5. Assignment 5, due Wed. 4/20, 11:59pm. Answer key
  6. Assignment 6, due Sat. 4/23, 11:59pm (See (3) of sample Prelim II key for main part of answer.)
  7. "Virtual A7, not graded, for exam review. Its answer key
  8. Main Project (A8), due 5/13 with checkpoint Mon. 5/9.
  9. Assignment 9, due Wed. 5/11, 11:59pm. Its answer key (handwritten); see also A9AVLkey.scala in /.../DATASTRUCTURES/ below.

Sample Final Exam (from Fall 2014 but translated into Scala; key will appear Thursday 5/19) Its Answer Key.

Prelim II Answer Key with extra notes on key handling and Scala quirks.

Sample Prelim I Practice Exam Its answer key

This is a Scala translation of the original in C++ given in Spring 2014. (FYI: The key to that version)

Sample Prelim II, again translated from C++. Its answer key (plain .txt)

Piazza Page for CSE250


Course Organization and Policies (syllabus updated for Spring 2022). Main possible differences from others' policies:

  • No lateness for reduced credit (nor earliness for plus credit). If in justifiable need of extension, request by e-mail to KWR at least 24 hours ahead of time.
  • No dropped assignments or quizzes or etc.---but a 5% reweighting policy (qualified by recitation attendance) that often has similar effect.
  • More will be said about attendance implementation and about submission logistics.

Last term's policies from "Incompletes" to the bottom of the page will all be followed.

Course topics in brief and roughly in order: Scala, list/sequence/queue/stack, asymptotic notation, recursion, linked structures (graphs), sorting, search trees (sorted data structures), hashing (unsorted data structures), advanced topics (B-trees and hierarchical storage; thread safety) as time allows.

Required Resources

1. Textbook: Object-Orientation, Abstraction, and Data Structures using Scala, Second Edition by Mark C. Lewis and Lisa L. Lacher.

2. A working Scala system, version 2.13.x or later but not Scala 3.

Other Resources

(will be added to, not all need be used)

CSE250 Course Resources in Scala Includes links to pages on official Scala site worth particular attention. (Old C++ course page and resources, for the curious)

Small Sample Scala Programs (Some will be shown in lectures.)

MaxWords area with Assignment 2 key (extending Assignment 1)

Scala Data Structures (for upcoming work after break)

Final Project Area (so far adds BST to above repo)

Quick-Reference Handout on Asymptotic Notation (by Tom Bylander of U.T. San Antonio, was given out in class on 9/14/11). Running Time Graphs by Jim Marshall of Sarah Lawrence. Slides on (``Algorithms and Complexity'') by Zeph Grunschlag, including examples of counting code statements, loops, and recursion.

Fibonacci Algorithms lecture by Prof. Hung Ngo, delivered in place of my own Fibonacci lecture with "BigInt' by TA Chris Kim on 2/11/13.

Red-Black Tree Deletion

Minimal Coding Guidelines, for submissions in this course.


Student Learning Outcomes

Upon completing this course, you will be able to... (per CS/CE categories)
  1. Compute, compare, and analyze runtime and function growth using asymptotic notation. (1,2,5,6/1,2,5,7)
  2. Identify functionality of basic data structures. (1,2,6)/(2,7)
  3. Identify the tradeoffs of different data structures, given their implementation. This also includes recognizing which situations benefit or suit the use of one data structure over another. (1,2,5,6/1,2,5,7)
  4. Use data structures in programming. (1,2,5,6/1,5)
  5. Implement and analyze basic algorithms such as searching and sorting, as well as recursive algorithms, tree traversal algorithms, and graph traversal algorithms. (1,2,5,6/1,2,5,7)
References: ABET, CS, CE. All will be touched by exams and written assignments, and programming itself will touch all but 1 and 3. As judged by the ABET guidelines, the CS outcomes 1,2,5,6 are supported, as are the CE outcomes 1 and 5, while CE 2 and 7 are minimally supported.