Lecture Notes for Computer Science 2530

January

February

March

April

May

Reference

	Coding standards
	Introduction to Linux
	Grading notes

Lectures

Part 1. C++ fundamentals, elementary algorithms and program development
1.	[M. January 7]
	Lecture 1A Introduction
	Lecture 1B The swamp

2.	[W. January 9]
	Assignment 0 assigned
	Lecture 2A Introduction to Linux
	Linux reference
	Lecture 2B Elementary C++ issues
	Lecture 2C Numeric types and expressions

3.	[Th. January 10]
	Lecture 3A Variables
	Lecture 3B Hand simulation
	Lecture 3C Abbreviations for assignments
	Lecture 3D Constants
	Lecture 3E Choosing variable names
	Lecture 3F Some uses of variables

4.	[F. January 11]
	Lecture 4A Functions
	Lecture 4B Side-effects and ignoring the value of an expression
	Lecture 4C Function libraries
	Lecture 4D Input and output
	Lecture 4E Writing to the standard output
	Lecture 4F Reading from the standard input

5.	[M. January 14]
	Lecture 5A Defining functions
	Lecture 5B What are functions good for?
	Lecture 5C What are parameters and what are they good for?
	Lecture 5D Programs and the main function
	Lecture 5E The order of function definitions
	Lecture 5F Standards for function definitions

6.	[W. January 16]
	Lecture 6A Mental model of functions 1: What does the function accomplish?
	Lecture 6B Avoiding the swamp: function contracts
	Lecture 6C Documenting a program
	Lecture 6D Other comments
	Lecture 6E Compound statements and scope

7.	[Th. January 17]
	Assignment 0 due
	Assignment 1 assigned
	Lecture 7A Boolean expressions
	Lecture 7B Making decisions
	Lecture 7C Mental model of boolean expressions
	Lecture 7D Standards for boolean expressions
	Lecture 7E Standards for if-statements

8.	[F. January 18]
	Lecture 8A While-loops
	Lecture 8B Planning loops
	Lecture 8C Loop invariants
	Lecture 8D Things to watch out for
	Lecture 8E Standards for loops
	Lecture 8F Nested loops and nested loop emulation

	[M. January 21]
	Holiday

9.	[W. January 23]
	Lecture 9A For-loops
	Lecture 9B Standards for for-loops
	Lecture 9C Breaking out of a loop
	Lecture 9D Elementary arrays

10.	[Th. January 24]
	Lecture 10 Loop algorithms 1: Scan algorithms

11.	[F. January 25]
	Assignment 1 due
	Assignment 2 assigned
	Lecture 10 Loop algorithms 2: Search algorithms

12.	[M. January 28]
	Exam 1 Lectures 3A, 3E, 4A, 4B, 5A, 6C, 7A, 7B, 7C,

13.	[W. January 30]
	Lecture 12A Avoiding the swamp: Diagnosing and fixing errors
	Lecture 12B Avoiding the swamp: Planning
	Lecture 12C Avoiding the swamp: Successive refinement
	Lecture 12D Avoiding the swamp: Using a debugger
	Lecture 12E Avoiding the swamp: Tracing

14.	[Th. January 31]
	Lecture 13A Mental Model of Functions 2: How Function Calls are Performed by the Computer
	Lecture 13B Recursion

15.	[F. February 1]
	Lecture 14A Understanding recursion
	Lecture 14B Recursive scan algorithms
	Lecture 14C Using equations

16.	[M. February 4]
	Assignment 2 due
	Assignment 3 assigned
	Lecture 15A Recursive search algorithms
	Lecture 15B Tail recursion

17.	[W. February 6]
	Lecture 16A Duplicated recursive calls
	Lecture 16B Discovering algorithms

Part 2. The memory and more C++
18.	[Th. February 7]
	Lecture 17A The memory, memory addresses and pointers
	Lecture 17B Hand simulation with pointers
	Lecture 17C Areas of memory

19.	[F. February 8]
	Lecture 18A Using the heap
	Lecture 18B Dangling pointers and memory faults
	Lecture 18C Memory leaks
	Lecture 18D Type definitions and const pointers

20.	[M. February 11]
	Exam 2 Lectures 8A, 8B, 9A, 9C, 10, 11, 13B.

21.	[W. February 13]
	Lecture 19 Parameter passing modes

22.	[Th. February 14]
	Lecture 20A Mental model of arrays
	Lecture 20B Creating and destroying arrays
	Lecture 20C Arrays and functions
	Lecture 20D Pointer arithmetic
	Lecture 20E Reallocating an array

23.	[F. February 15]
	Assignment 3 due
	Assignment 4 assigned
	Assignment 4
	Lecture 21A Modules
	Lecture 21B Standards for modules

24.	[M. February 18]
	Lecture 22A Structures
	Lecture 22B Constructors
	Lecture 22C Pointers to structures

25.	[W. February 20]
	Lecture 23A Naming and documentating structures
	Lecture 23B Forward and recursive structure type definitions
	Lecture 23C Copying structures
	Lecture 23D Passing structures to functions
	Lecture 23E Arrays of structures

Part 3. Data structures and algorithms
26.	[Th. February 21]
	Lecture 24A Abstract data types
	Lecture 24B Conceptual Lists
	Lecture 24C Linked lists
	Lecture 24D Implementation of linked lists

27.	[F. February 22]
	Assignment 5 assigned
	Assignment 5

	[Sat. February 23]
	Assignment 4 due

28.	[M. February 25]
	Exam 3 has been moved to February 27.
	Lecture 25A Equations about lists
	Lecture 25B Defining list functions by equations

29.	[W. February 27]
	Exam 3 Lectures 13B, 14A, 14B, 15A, 17A, 17B, 17C, 18A, 18B, 18C, 20A, 20B, 20C.

30.	[Th. February 28]
	Lecture 26 More examples of functions on lists

31.	[F. March 1]
	Lecture 27A Destructive functions on linked lists
	Lecture 27B Memory sharing

	[M. March 4 – F. March 8]
	Spring break

32.	[M. March 11]
	Assignment 5 due
	Assignment 6 assigned
	Assignment 6

33.	[W. March 13]
	Lecture 28 Looping over linked lists

34.	[Th. March 14]
	Lecture 29A FIFO queues
	Lecture 29B Linked implementation of FIFO queues
	Lecture 29C Array implementation of FIFO queues

35.	[F. March 15]
	Lecture 30A Characters
	Lecture 30B Null-terminated strings

36.	[M. March 18]
	Exam 4 Lectures 20A, 20B, 20C, 20D, 22A, 22B, 22C, 23C, 23D, 24B, 24C, 24D, 25A, 25B, 26, 27A, 27B, 28.

37.	[W. March 20]
	Assignment 6 due
	Assignment 7 assigned
	Assignment 7

38.	[Th. March 21]
	Lecture 31 Algorithms on null-terminated strings

39.	[F. March 22]
	Lecture 32A Reading and writing strings and characters
	Lecture 32B Writing files
	Lecture 32C Reading files

40.	[M. March 25]
	Lecture 33A Binary Trees
	Lecture 33B Trees in C++
	Lecture 33C Nondestructive functions on trees

41.	[W. March 27]
	Lecture 34A Traversing trees
	Lecture 34B Destructive functions on trees

42.	[Th. March 28]
	Lecture 35A Elementary analysis of algorithms
	Lecture 35B Analysis examples
	Lecture 35C Profilers

43.	[F. March 29]
	Lecture 36A Linear and Binary Search
	Lecture 36B Binary search trees

44.	[M. April 1]
	Exam 5 Lectures 29A, 30A, 30B, 31, 33A, 33B, 33C, 34A, 34B, 35A.

45.	[W. April 3]
	Lecture 37 Inserting and removing the smallest for binary search trees

46.	[Th. April 4]
	Assignment 7 due
	Assignment 8 assigned
	Assignment 8

47.	[F. April 5]
	Lecture 38A Deletion from a binary search tree
	Lecture 38B Height-balanced binary search trees

48.	[M. April 8]
	Lecture 39 Keeping a binary search tree height-balanced

49.	[W. April 10]
	Lecture 40A Tables
	Lecture 40B Hash tables

50.	[Th. April 11]
	Lecture 41 Heaps and priority queues

51.	[F. April 12]
	Lecture 42A Sorting
	Lecture 43 Heapsort

52.	[M. April 15]
	Exam 6 Lectures 36B, 37, 38B, 39, 40B, 41,

53.	[W. April 17]
	Lecture 42B Merge Sort
	Lecture 42C Implementation of Merge Sort for linked lists

54.	[Th. April 18]
	Review

	[F. April 19]
	Holiday

55.	[M. April 22]
	Assignment 8 due
	Review

56.	[Tu. April 23]
	(Today is treated like a Friday) Review

	[W. May 1]
	Final exam for section 001: 11:00–1:30 Final exam for section 002: 2:00–4:30