NPRG030 Programming I (winter 2017-8)

Instructor: Adam Dingle

This course is a fast-paced introduction to programming and to data structures and algorithms, with a strong emphasis on learning to write working code. It assumes no previous programming experience.

The course has two major goals.

First, we will learn the Pascal programming language, mostly in the first six weeks of the course. Specifically, we will use the dialect of Pascal understood by the Free Pascal compiler (but without any of its object-oriented extensions: classes, methods and so forth).

Second, we will study fundamental data structures and algorithms and learn to analyze their computational complexity.

Throughout the course students will complete many programming exercises in Pascal, both to implement the algorithms we study and also to solve a wide variety of other programming problems.

Lectures and other meetings


This is a pass/fail course: you will not receive a numeric grade.

To pass this class, you must fulfill the following requirements by February 18, 2018 (the end of the exam period):

  1. Complete a number of programming exercises through the semester. I will assign these exercises weekly, and you can submit your solutions to the ReCodEx automated grading system.

    To pass, you will need to earn at least 140 points, i.e. 70% of the points that are possible for the 20 exercises that were assigned through December. (During January I have assigned some additional ReCodEx exercises that may allow you to earn extra points if you have fallen short.)

  2. Pass a written exam at the end of the semester. This exam will take place on Tuesday, January 23rd from 10:30 – 12:45 in room S4.

  3. Write a program in Pascal as a semester project. Your program should accomplish something that is interesting, cool, or fun and can be 100-300 lines long, or longer if you like. Here are some possible ideas for projects.

    I highly recommend that you submit your program to me by the week of February 4. That will give me time to give you feedback and for you to revise your program if necessary. I will not accept any work submitted after February 18th.

  4. Regularly attend the lectures and tutorials and participate in class.


There are many copies of Introduction to Algorithms in the MFF library on the first floor above the computer lab.



This is a rough map of the ground we plan to cover in this class, with plenty of interesting twists and turns along the way.

October 10 (lecture notes) (exercises)
Course overview, requirements for course credit. Pascal program structure. Variables, constants, assignment. Primitive data types (integer, boolean, real, char). Reading/writing to/from the console. Basic control structures (if, for, while, repeat). Arithmetic and boolean operators. Strings. (McBride, chs. 1-2)
October 17 (lecture notes) (exercises) (tutorial notes)
More control structures (case, goto, break, continue). Arrays. (McBride, chs. 2-3)
October 24 (lecture notes) (exercises)
Ranges. Enumerated data types. Functions and procedures, global and local variables. Passing parameters by value and reference. A first look at recursion. Dividing an integer into digits, positional notation for numbers. Linear and binary search in sorted arrays. (McBride, ch. 4)
October 31
No lecture (matriculation ceremony).
November 7 (lecture notes) (exercises)
Records. Text and binary files. Analyzing worst-case and best-case running times. Introduction to asymptotic (big-O) notation. Divisibility, primality testing, factorization. (McBride, ch. 6)
November 14 (lecture notes) (exercises) (tutorial notes)
More on recursion. Time complexity of recursive functions.
November 21 (lecture notes) (exercises)
Pointers and dynamic memory allocation. Linked lists. The sieve of Eratosthenes. (McBride, ch. 7; Cormen, chs. 3.1,10.2)
November 28 (lecture notes) (exercises) (tutorial notes)
Bubble sort, insertion sort. Divide and conquer, mergesort. Stacks. Binary search trees. (Cormen, chs. 2, 10.1, 12)
December 5 (lecture notes) (exercises)
Function pointers. Queues. Quicksort. Euclid's algorithm. (Cormen, chs. 7, 10.1, 31.1-31.2)
December 12 (lecture notes) (exercises)
Heaps and heapsort. Representing and evaluating arithmetic expressions. Variant records. (Cormen, ch. 6)
December 19 (lecture notes) (exercises)
Graph representations. Depth-first search, breadth-first search, Dijkstra’s algorithm. Backtracking. (Cormen, chs. 22.1-22.3, 24.3)
December 26
No lecture (winter vacation).
January 2
No lecture (winter vacation).
January 9 (lecture notes) (practice exam) (practice exam solutions)
Counting sort and radix sort. More asymptotic notation. Higher-precision arithmetic (“long numbers”). (Cormen, chs. 8.1-8.3, 18)