CSCI.2300 Introduction to Algorithms.
Programming Language Essentials. Functional, Concurrent, and Logic Programming Paradigms.
When the students have successfully completed this course, they will be able to:
|09/01||Introduction to programming languages: history, essentials, syntax, semantics, paradigms.||ppt pdf functions.oz functions.hs||PDCS Chapter 2|
|09/04||Lambda calculus: alpha-renaming, beta-reduction, applicative and normal evaluation orders, Church-Rosser theorem, combinators||ppt pdf combinators.oz eta.oz combinators.hs eta.hs||PDCS Chapter 2|
|09/08|| Lambda calculus: higher order programming, eta-conversion,
recursion combinator, numbers, booleans
||all ppt pdf rec.oz lambda-numbers.oz lambda-numbers.hs lambda-booleans.oz lambda-booleans.hs hop.oz hop.hs||PDCS Chapter 2|
|09/11|| Functional programming: lists, records, pattern matching,
recursion (Haskell, Oz)-- Programming Assignment 1 Due 09/24
||PA1 description PA1 description in pdf
all 2015/09/11 handouts ppt pdf pascal.oz pascal.hs lists.oz lists.hs comb.oz comb.hs
|CTM Chapters 1.1-1.7, 3.2, 3.4.1-3.4.2|
|09/15||Higher order programming: closures, procedural abstraction, genericity, instantiation, embedding.||ppt pdf sqrt.oz sqrt.hs||CTM Chapters 3.2 and 3.6.1|
|09/18||Control abstractions: map, reduce, iterate, fold, filter||ppt pdf explicit-lazy.oz mapreduce.oz iscombinator.oz iscombinator.hs mapreduce.hs||CTM Chapters 1.9, 3.6 and 4.7|
|09/22||Lazy evaluation, set comprehensions||ppt pdf lazy-eval.oz lazy-eval.hs||CTM Chapters 1.8 and 4.5|
|09/25||Type checking and type inference, abstract data types, monads||all pptx pdf type-limitations.hs stackADT.oz stack.hs list-monad.hs count-monad.hs||CTM Chapters 2.8.3 and 3.7, EPL Chapter 4, GIH Chapter 9|
|09/29||Review for Exam 1||ppt pdf|
|10/06||Actors: a model of concurrent computation||ppt pdf||PDCS Chapter 4|
|10/09||Actor programming languages (SALSA, Erlang)||ppt pdf Cell.salsa CellTester.salsa cell.erl cellTester.erl||PDCS Chapter 9, CPE Chapter 5|
|10/16||Concurrency control abstractions -- Programming Assignment 2 Due 10/29||All ppt pdf fibonacci/Fib.salsa fibonacci/FibonacciTester.salsa fibonacci/JoinCont.salsa fibonacci.erl treeprod/Tree.java treeprod/TreeProduct.salsa treeprod/TreeProductTester.salsa treeprod/JoinCont.salsa treeprod.erl||PDCS Chapter 9, CPE Chapter 5|
|10/20||Distributed systems abstractions||All ppt pdf dcell/Cell.salsa dcell/CellTester.salsa dcell/GetCellValue.salsa dcell.erl dcellClient.erl dcellTester.erl addressbook/AddressBook.salsa addressbook/GetName.salsa addressbook/GetEmail.salsa addressbook/AddUser.salsa addressbook/MigrateBook.salsa addressbook_client.erl addressbook.erl||PDCS Chapter 9, CPE Chapter 6|
||Mobility (SALSA) and fault-tolerance (Erlang) abstractions; garbage collection, visualization (SALSA), hot code loading (Erlang)||All pptx pdf migrate/Migrate.salsa dcell/MovingCellTester.salsa addressbook/MigrateBook.salsa addressbook_exception.erl||PDCS Chapter 9, CPE Chapter 7|
|10/27||Object-oriented programming: inheritance, polymorphism (Oz, Java)||All ppt pdf oop.oz mm/c.java dd/c1.java dd/c2.java dd/c3.java||CTM Chapter 6.1--6.4 and 7.1--7.2|
||Declarative concurrency: dataflow variables, suspendable statements (Oz)||pdf ppt dconcurrency.oz||CTM Chapters 1.10-1.16, 4.1-4.4, 4.6|
|11/03||Review for Exam 2|
|11/10||Predicate calculus, first-order logic, Horn clauses, Clocksin-Mellish procedure.||ppt pdf students.pl||PLP Chapter 11, CTM Chapter 9.3.1|
||Terms, Resolution, Unification, Search, Backtracking (Prolog); Relational Computation Model (Oz)||ppt pdf rainy.pl rainy.oz students2.pl||PLP Chapter 11 and CTM Chapter 9.1|
||Prolog Imperative Control Flow: cut(!), call, fail, not, repeat, findall. Closed-world assumption, generate-and-test. Lists, Append relation (Prolog, Oz). -- Programming Assignment 3 Due 12/03||All ppt pdf PA3 loop.pl family.pl family.oz cut.pl cut2.pl cut3.pl cut4.pl cut5.pl append.pl append.oz||PLP Chapter 11, CTM Chapter 9.3.2--9.3.4|
||Constraint satisfaction problems, propagate-and-search, natural language parsing (Definite Clause Grammars)||All ppt pdf crossword.pl digit.oz propagate-search.oz constraints.oz sentences.pl sentences2.pl sentences3.pl||PLP Chapter 11, CTM 9.2, 9.4, 12.1--12.2|
|11/24||Prolog I/O, equalities, types, operators; Databases: assert, retract||All ppt pdf browse.pl tictactoe.pl insertsort.pl member.pl member.oz graph-db.oz||PLP 11, CTM 9.6|
|12/01||Accumulators, Difference Lists (Prolog, Oz)||All ppt pdf accumulators.pl accumulators.oz dlists.pl dlists.oz nestedloop.pl||CTM 3.4.3, CTM 3.4.4|
|12/04||Constraint Programming: Computation Spaces (Oz)||ppt pdf rectangle.oz palindrome.oz sendmoremoney.oz||CTM 12.3--12.5|
|12/08||Review for Exam 3|
The course consists of three main parts, covering respectively functional, concurrent, and logic programming. Evaluation for each part includes a programming assignment and a partial exam.
For functional programming, we will use Haskell and Oz. For concurrent programming, we will use SALSA and Erlang. For logic programming, we will use Prolog and Oz. You can choose any of the two supported programming languages per paradigm for programming assignments. Programming assignments can be done either individually or in pairs. Do not show your code to any other group and do not look at any other group's code. Do not put your code in a public directory or otherwise make it public. You are encouraged to use the LMS Discussions page to post questions so that other students can also answer/see the answers. There will be three grace days for late submissions throughout the semester, to be used in any combination of PAs, e.g., PA1 may be one day late and PA3 may be two days late, as long as PA2 was submitted on time. Late assignments beyond the three day grace period will receive a grade of 0.
Students may use for reference during exams: physical textbooks, printed course slides, and one personal one-sided crib sheet. No electronics will be allowed. All exam answers must be the student's own. Exam grades may be curved.
We will use an adaptive weighting scheme for grades: The best two programming assignments will have a total grade weight of 40% (20% each), while the third one will have a weight of 10%. We will use the same adaptive weighting scheme for partial exams: the best two exam grades will be worth 40% of the total grade with the third one counting for 10% of the total grade. Final letter grades will then be assigned as follows:
Please contact the instructor if there is any question about academic (dis)honesty.