Afghan eQuality Alliance
This is an English-language course for Computer Science students. It uses selections from lectures on Introduction to Algorithm Analysis. The lectures were recorded at the Massachusets Institute of Technology (MIT) in 2005. Most of the selections come from the first lecture.
The course consists of eight units. Each unit can take one or two weeks, depending on the level of the students and the needs of the course. Units are divided into short segments. Each segment consists of the transcript of what the lecturer says and two commentaries. The first commentary is a paraphrase of the transcript. It explains what the lecturer says in simple words and sentences. The other commentary explains the grammar and difficult words or expressions in the segment.
Within each unit, there are two kinds of material: the content discussed in the unit, and English grammar and vocabulary used in the unit. In the table below, we give brief descriptions of the content and the English material of each unit.
For each unit, we also provide versions that hide some material from the student: the transcript, the glossary, or both. These versions are used for exercises.
We recommend that students follow this process:
READING: Read the paraphrase through, using the glossary.
LISTENING COMPREHENSION: Work through the unit segment by segment listening to the movie, reading the grammar-vocabulary comments and looking up words in the glossary.
DICTATION: Using the version without the transcript, listen to the movie segment by segment and write down what the lecturer says.
TRANSLATION: Translate the paraphrase into your native language.
SUMMARY: Using the version without the transcript or paraphrase, listen to each segment and write down a short summary of what the lecturer says.
By the end of the course, students will reach these objectives:
In computer science, they will learn or review the problem of sorting, the Insertion sort and Merge sort algorithms, and the main ideas of algorithm analysis:
| Unit | Description |
|---|---|
| 1. Content | Students will learn how courses in American universities are organized and administered. |
| 1. English | English tenses, especially in conditional clauses. The future tense. |
| 2. Content | More organizational material. Attendance and grading policies; policies on joint work and cheating. |
| 2. English | Colloquialisms. Progressive tenses. Count and mass nouns. Irregular plurals. |
| 3. Content | The sorting problem. The Insertion Sort algorithm. Pseudocode. Loop invariants |
| 3. English | Features of spoken language: connectives and fillers. Contrary-to-fact conditionals and the use of would. |
| 4. Content | Example of sorting by Insertion Sort. Beginning of analysis. |
| 4. English | Same as in Unit 3, with more examples. |
| 5 Content | Kinds of algorithm analysis: worst case and average case. Why the average case analysis is more difficult. |
| 5 English | More features of spoken language. |
| 6 Content | Machine-independent algorithm analysis. Asymptotic analysis. Theta notation and other notations, including big O notation. |
| 6 English | Expressions: let's see; look at, take a look at; kind of; sort of. Contrary-to-fact conditions: If I were... |
| 7 Content | Worst-case analysis of Insertion sort. Why is it Theta(n^2)? Arithmetic progression. Strong and weak notations. |
| 7 English | colloquial speech: use of There's for "there is" and "there are" |
| 8 Content | Rigorous definition of Big-O notation. Properties of Big-O notation. It is not symmetric even though it has equal sign in it. |
| 8 English | direct objects with infinitives: I want X to do Y |