Data Structures and Algorithm Design

This opening session does three jobs. It explains how the course actually runs and how it is graded. It builds, from scratch, the working definition of an algorithm and the five properties every algorithm must have. And it sets up the first tool we will use to measure how fast an algorithm is — the RAM model with primitive operations — before showing why we will replace it with a more practical method.

1.1 Course Format and Study Workflow

1.1.1 A Flipped-Mode Course

The course is offered in flipped mode. That means roughly 10 to 11 live sessions are set aside for the application part of the work: coming to class, working through examples, and using what you have already studied. The concepts themselves come from recorded lectures that students must watch before each live session.

Think of it like learning to cook from a video and then going to a kitchen workshop. The video is where you hear the techniques once, at your own pace; the workshop is where you actually chop, stir, and make mistakes under supervision. Neither alone is enough — watching a video without practicing leaves you without skill, and practicing without watching leaves you lost in the kitchen. In this course, the recorded lectures are the video, and the live session is the kitchen. The analogy breaks in one place: in a kitchen workshop the instructor watches everyone at once, while here you are expected to bring your own preparation to every session, and the class builds on it.

The first 10 to 15 minutes of every session include a quick revision of the important topics from the recordings, so even someone who could not get through them gains something by attending. Still, the standing advice is clear: watch the recorded lectures before you come, because otherwise you lose out on at least a few points. The revision is a skim — the full depth lives in the recordings.

The recordings are not a substitute for class. Several topics get re-explained live from a different angle, with a different example. Some algorithms from the recordings get re-analyzed from a different perspective altogether — because no algorithm can be viewed from only one side. There are many ways to look at how an algorithm works, how to analyze it, and how to understand its complexity. Both student cohorts (SC and SS) sit in the same sessions, and the core structure of the course is the same for both programs, so there is no need to worry about which program you belong to.

1.1.2 The Contact-Session Plan and the Recorded Lectures

The handout contains the full picture of how the course is run. The course content structure lists the topics with suggested hours next to each — but those hours are the ideal case, so do not treat them as binding; the course simply takes the time it takes. The handout also lists learning outcomes to check after the course, so you have a concrete way to test whether you actually learned what the course promised.

Part B of the handout is the contact-session plan: what to do before each contact session, what happens during it, and what to study after it. This before/during/after rhythm is the operating loop of the whole course — each session has a pre-contact step (go through the corresponding recorded lecture), a during-contact step (the live application work), and a post-contact step (study the material). The plan is spelled out for every contact session, so you never have to guess what is expected of you.

The recorded lectures live in the courseware section of the eLearn portal, organized by modules and topics — for example, module AD 1.1 with its materials and its recorded lecture. The expectation is to complete the entire 1.x series before coming to the class that follows it. If you are not sure which recordings to cover, the list is spelled out per module and topic; you do not have to guess. This organization matters in a flipped course because the recordings are the primary source of concepts — missing one module silently breaks the chain of understanding for the live session that depends on it.

1.1.3 The Merged Course Version

The portal lists the same course twice, once as a flipped version and once as a merged version. The material inside is identical; the merged version is the one to refer to.

The practical takeaway: when two entries for the same course appear on the portal, this is not a choice between two different courses — it is the same course appearing under two labels. Pick the merged version and use it consistently, and every week's materials will be under that week's topic heading.

Real-world connection: this flipped structure is the same model used in corporate training and professional certification programs, where employees watch vendor-provided modules at home and then attend instructor-led workshops to apply them. The habit of "study first, apply second" is not just a course rule — it is the standard rhythm of self-paced professional development. Within this course, the same rhythm reappears in every topic: the recorded lecture builds the concept, and the live session re-derives and re-analyzes it from a different angle.

1.2 Evaluation Scheme and Exam Plan

1.2.1 EC1: Assignments and Quizzes (30%)

Every course has three evaluation components: EC1, EC2, and EC3. For this course, EC1 is worth 30% and is made of quizzes plus assignments. The updated weightages, as stated in the session, are:

Reconciled note on the numbers. The session stated Assignment 1 = 12% and Assignment 2 = 13% twice in the spoken discussion ("Assignment 1 will contribute to 12% of the total weightage. And assignment 2 will contribute to 13%"), and the combined assignment weightage of 25% (12 + 13) matches the explicit statement that "assignments contribute to 25%". A single slide-reading pass sounded like "Assignment 2 for 12", but the spoken weightages and the 25% assignment total confirm 12 + 13. Use Assignment 2 = 13%.

The two quiz scores are averaged and that average is scaled down to 5% of the total. So the two assignments together contribute 25% and the quizzes contribute 5%, giving EC1 = 30%:

$$\text{EC1}=\underset{\text{assignments}=25\%}{\underbrace{12\%+13\%}}+\underset{\text{quiz average}}{\underbrace{5\%}}=30\%$$

The apparent puzzle "5 + 12 + 13 + 5 = 35, not 30" dissolves once you see that the two quizzes do not add as two separate 5% chunks. The quiz average is scaled down to a single 5% contribution, so the raw individual quiz weights are not summed into EC1 — the scaled average is. The handout was updated with these numbers, so anyone who downloaded an earlier copy should fetch the new one to avoid confusion.

1.2.2 Quiz Format

There are only two quizzes in the whole semester, one after the other — not a quiz in every class. Each quiz runs for one hour, but it stays open for a stretch of days (roughly a week; the exact window is communicated centrally). Once you start attempting, you get only that one hour of time limit. The average of the two quizzes is taken and scaled to 5%. The rollout date and the due date will be announced on the portal.

1.2.3 Exams: Mid-Semester and End-Semester

EC2 is the mid-semester exam: 30% of the total, 2 hours long. Its syllabus is the material from contact sessions 1 to 5 — and "contact sessions 1 to 5" means all the recorded lecture content plus the contact hours up to contact hour 10. So when you prepare for the mid-semester exam, the scope is not just what happened in five live sessions; it includes the full recorded lecture content that those sessions were built on, covering material up to contact hour 10.

EC3 is the end-semester exam: 40% of the total, 2.5 hours long. The end-semester exam does not only cover topics after the mid-semester point; it includes all the topics in the syllabus. The split between pre-mid-semester and post-mid-semester material inside that paper is adjusted based on how the class performed in the mid-semester exam — the professor mentioned possible splits like 60/40, 70/30, or 75/25, varying from year to year.

Real-world connection: this graded-component structure mirrors how professional certifications and company learning programs allocate weight — continuous assessment (assignments, quizzes) carries a sizable share, and a final comprehensive exam pulls everything together. The habit of checking weightages before allocating study time is the same habit you use to prioritize work in any project with a scoring rubric.

1.3 Textbooks and Learning Resources

1.3.1 Primary Textbook

The main textbook is Algorithm Design: Foundations, Analysis, and Internet Examples by Goodrich. Online versions are available for download. This is the book the course follows for the main treatment of each topic — its level matches the pace of the course, and its examples are the ones the live sessions build on.

1.3.2 Reference Textbook

The reference textbook is Data Structures, Algorithms, and Applications in Java by Sartaj Sahni. The same book also exists in a Python version, so you can pick the one you are comfortable with. The key point is that the choice of programming language does not force a choice of book: whether you implement in Java or Python, the same reference covers you.

1.3.3 CLRS — The Bible of Algorithms

Introduction to Algorithms by Cormen (commonly called CLRS) is known as the Bible of Algorithms. It is not the primary textbook, because its treatment is more advanced. The recommended route is to master a concept with the primary textbook first, then read the corresponding Cormen chapter — you will get a very thorough understanding of the same topic from a different perspective. The professor's honest warning: if you try Cormen before the concept is clear, you will feel that you understood nothing; once the concept is clear, the same chapter gives a deep, rigorous second view. All three books are equally useful, and the online versions can be downloaded.

Real-world connection: this "read it twice from two sources" habit mirrors how working engineers learn a new technology — a gentle tutorial first, then the official specification or dense reference. Each pass adds the perspective the other one lacks, which is exactly why the course keeps returning to the same algorithms from different angles throughout the semester.

1.4 What Is an Algorithm

A quick poll of what students remember from earlier studies of data structures and algorithms mostly came back empty, with sorting, searching, and binary search as the survivors. That is a starting point, not an end point: this course begins at a balance between basic and advanced topics, and "binary search and sorting" as the entire answer to "name some algorithms" is not enough — we will go far beyond naming algorithms.

1.4.1 The Definition, Built From Student Answers

The opening question is the simplest one in the course, and the standard is set for the whole semester: even at midnight, if someone calls, you should be able to answer what an algorithm is. The class offered definitions and each one was graded on a one-mark scale, which shows exactly where the definition lives:

The marking pattern is the lesson: each piece you name moves you up the scale, and the word that separates a 0.75 answer from a 1.0 answer is unambiguous. That full sentence is the working definition of the course:

1.4.2 The Four Pieces of the Definition

The definition has four load-bearing pieces:

1. Step-by-step instructions — the algorithm is a sequence, not a single idea. A single instruction is not an algorithm; the ordering of the steps is part of the meaning.
2. To accomplish a given task — the instructions point at one concrete goal. An algorithm without a goal is just a list of operations.
3. Finite — the sequence comes to an end in a finite number of steps or in finite time. If the sequence never ends, it can never be followed to completion.
4. Unambiguous — every instruction has exactly one meaning. No instruction may leave room for two different interpretations.

Students produced the first three easily; the word that was missing from every early answer was unambiguous, and it is the one that turns a list of instructions into an algorithm. Intuition for the fourth piece: think of a recipe where "cook until it looks right" appears — two different people will stop cooking at two different moments. Unambiguity is what makes the outcome independent of who is executing the steps.

1.4.3 "Bake Until Done" Is Ambiguous

Here is a test of unambiguity. A brand-new baker is told: bake until done. Ambiguous or unambiguous? Ambiguous — the baker does not know what "done" means for a cake, nor how to check. The fix is to add a checking step: insert a toothpick, take it back out, and if nothing sticks to it, consider the cake done.

The point of the example: even one vague statement makes the whole instruction set ambiguous. It does not matter that the other nine steps are perfect — a single ambiguous step poisons the algorithm.

1.4.4 "Choose a Large Number" Is Ambiguous

Consider the instruction: choose a large number. Ambiguous. A five-year-old standing next to you will pick 20, because 20 is the largest number they studied last week. For us, "large" might mean one million or one billion. The word has its own definition inside each person's head, so the instruction must say what large means. You have to be very clear about what you mean.

1.4.5 The Peanut-Butter-and-Jelly Sandwich

A slightly more complex example. Take two pieces of bread. Put peanut butter on one side of one piece. Put jelly on one side of the other piece. Put the pieces together. Is this algorithm ambiguous? Yes — the last step does not say how to put the pieces together. The correct instruction must say the pieces go together with the peanut butter and jelly on the inside; otherwise the result is a messy sandwich. The class split on this one, and the student who answered correctly explained that the two spread sides have to face each other. Every statement in an algorithm must be unambiguous for the algorithm to be effective.

1.4.6 Ambiguity of the Whole vs. Ambiguity of Each Statement

The relationship is bottom-up: the whole algorithm earns the label "unambiguous" only if every single statement already earned it. There is no shortcut where a confusing step is forgiven because the algorithm as a whole has one clear purpose.

1.4.7 From Problem to Output

The notion of an algorithm sits in a pipeline:

Problem → Algorithm → Program → Computer (with input) → Output

There is a problem; we write an algorithm for it; that algorithm is converted into a program; the program is fed into a computer together with an input; and we expect an output. Everything we do this semester lives in the first two stages of that pipeline: taking a problem and designing an algorithm for it — before any program, language, or machine enters the picture. This is also the boundary that defines the course's focus: the analysis of the algorithm happens at the design stage, not at the execution stage, a theme that returns in Section 1.7.

Real-world connection: this pipeline is exactly how software is built in industry — a requirements problem is turned into an algorithm or design, that design is implemented in code, and the code runs on machines with live input. Companies care most about the quality of the middle two stages, and this course trains the first two: the problem and the algorithm.

1.5 Properties of an Algorithm

Beyond the definition, an algorithm is expected to have five properties: input, output, finiteness, definiteness, and effectiveness. These five are midnight-call material — you should be able to list and explain all of them at any hour.

1.5.1 Input: Zero or More

An algorithm takes zero or more inputs. A simple example: an algorithm that prints a fixed name needs no input at all — everything it needs is already written into the algorithm. "Input" means something fed into the algorithm during execution, at runtime — not values that are hard-coded into the algorithm itself. Whenever an algorithm does have an input, the range of inputs for which it works must be specified very carefully. The header of every algorithm you write should state the expected input and the expected output in plain words, so that the range of valid inputs is documented before the first step is read.

1.5.2 Output: At Least One

An algorithm produces at least one output. Sometimes you cannot see the output directly on a screen; it may be an action, like sending an email, initiating a phone call, or escalating a problem. Whatever form it takes, the algorithm should produce a correct result. The contrast with input is deliberate: input can be zero or more, but output must be at least one — an algorithm that produces nothing is not performing its task.

1.5.3 Definiteness

Definiteness is the property of clarity. Each instruction of the algorithm must be clear and unambiguous — the same idea that carried the definition of an algorithm. Where unambiguity in the definition describes the whole sequence, definiteness here is the per-instruction requirement: when the algorithm executes, no instruction may leave the executor wondering what to do next.

1.5.4 Finiteness

The algorithm must come to an end after a finite number of steps. An algorithm that keeps working forever is useless. A non-ending while loop or a non-ending for loop has no use; termination after a finite sequence of steps is mandatory.

1.5.5 Effectiveness

That is the key correction of the section: effectiveness is about each instruction pulling its weight in the input-to-output transformation, not about how optimized the algorithm is.

1.5.6 The Midnight-Call Test

The five properties — finiteness, definiteness, effectiveness, input, and output — are the standard checklist. If someone asks "what are the properties of an algorithm" at midnight, you should be able to answer without thinking. The reliable order to recite them: input, output, finiteness, definiteness, effectiveness — and for each, the one-line explanation. This checklist is also the verification tool used in Section 1.6, where a given procedure is checked property by property before being called an algorithm.

Real-world connection: these five properties are the acceptance criteria a code reviewer applies to any procedure in industry. Does it take input correctly (and document its range)? Does it produce output (even an action like sending an email)? Will it stop (no infinite loops)? Is each instruction clear? Does every statement contribute to the result? A procedure that fails any one of these five is rejected before any performance discussion starts.

1.6 Euclid's Algorithm

Euclid's algorithm is a simple algorithm everyone knows from school, but it is worth re-reading as the model example: it shows how a properly written algorithm looks — header included — and how to verify that a given procedure really is an algorithm.

1.6.1 The Algorithm and Its Header

The header states everything the algorithm promises — this is the pattern every algorithm header in the course must follow:

• Algorithm name: Euclid
• What it does: computes the greatest common divisor (GCD) of M and N by Euclid's algorithm
• Input: two non-negative integers M and N, not both zero
• Output: the greatest common divisor of M and N

The steps:

1. If $N=0$, return the value of $M$ as the answer and stop. Otherwise proceed to step 2.
2. Divide $M$ by $N$ and assign the value of the remainder to $R$:

$$R=M\mathrm{mod}N$$

where $M\mathrm{mod}N$ is the remainder left when $M$ is divided by $N$.

1. Assign the value of $N$ to $M$, and the value of $R$ to $N$. Go back to step 1.

Only "not both zero" is fixed about the inputs — one of them may be zero, and that is exactly what step 1 catches on the very first check. If $N=0$ from the start, the algorithm returns $M$ immediately, which matches the mathematical fact that $\gcd (M,0)=M$.

1.6.2 Worked Example: The GCD of 6 and 10

Find the GCD of 6 and 10. The input spec does not say which number must be called $M$; it only says the two numbers are non-negative and not both zero. In the worked example the professor fixed $M=6$ and $N=10$ — which triggered an important exchange:

The reconcile note on this exchange: the professor first mentioned that writing $M=10$ and $N=6$ is also permitted, and then ran the worked example with the chosen assignment $M=6,N=10$, whose first remainder is 6. Starting from the alternative assignment $(10,6)$ instead would produce the same final answer — the algorithm reaches $\gcd (6,10)=2$ from either ordering, because the GCD is symmetric in its inputs. The trace below follows the professor's chosen assignment.

With $M=6,N=10$ the full trace is:

The pairs visited are $(6,10)\to (10,6)\to (6,4)\to (4,2)\to (2,0)$. Since step 1 now sees $N=0$, the algorithm returns $M=2$ and stops. So the greatest common divisor of 6 and 10 is 2:

$$\gcd (6,10)=2$$

1.6.3 Why This Algorithm Is Finite

$$0\le M\mathrm{mod}N<N$$

This inequality is the mathematical engine of the algorithm. Dividing any non-negative integer $M$ by a positive integer $N$ leaves a remainder that is never negative and never reaches $N$ — it is always strictly smaller than $N$. Because step 3 installs $R=M\mathrm{mod}N$ as the new $N$, the second number of the pair is forced to shrink with every iteration: $10,6,4,2,0$. A strictly decreasing sequence of non-negative integers cannot keep going forever; it must hit 0 sooner or later, and when it does, step 1 fires and the algorithm stops. That decreasing property is what makes the algorithm finite — a guarantee, not a hope.

1.6.4 Checking All Five Properties

After the trace, the class checked the algorithm against the definition and the five properties:

• Input: yes — two non-negative integers, not both zero.
• Output: yes — the greatest common divisor.
• Finiteness: yes — the second number of the pair strictly decreases each iteration because a remainder is always less than the divisor, so it must reach zero.
• Unambiguous: yes — no step left anyone stuck; every step was clear.
• Effectiveness: yes — every step takes the computation one step closer to the output.

Since all five properties hold, we can boldly call it an algorithm — and this is the way to look at any algorithm you are handed.

1.6.5 The Discussion Question: What Is Not an Algorithm

The reverse question is posted as a discussion thread: give an example of an instruction set that is not an algorithm. The hint is that there are many ways to fail — a set of instructions can be infinite, it need not come to an end, it can be ambiguous, or it can lack an exit condition. The algorithm above stops on $N=0$, but another algorithm might stop on $N=1$; what matters is that some exit condition exists.

Real-world connection: Euclid's algorithm is the workhorse behind public-key cryptography — systems like RSA rely on computing GCDs of enormous integers, where a naive trial-and-error approach is impossible but the remainder-driven loop finishes in only a handful of iterations even for numbers with hundreds of digits. The same algorithm also simplifies fractions, finds least common multiples via $\mathrm{lcm}(a,b)=ab/\gcd (a,b)$, and lies at the heart of number-theoretic computations used across computer science.

1.7 Efficiency: Space and Time

1.7.1 The Aim: The Most Efficient Algorithm

The goal of the course is to design the most efficient algorithm for a given problem. "Efficient" has two faces: space efficiency and time efficiency.

1.7.2 Space Efficiency Is No Longer the Bottleneck

Space efficiency is no longer a major concern, because storage space is available at cheap cost these days. Cloud storage is there: even if you cannot afford a machine with huge storage capacity, you can use cloud services and get the storage you need.

"Space" in this context means three things. Program space is the space required to store the machine-level program generated by the compiler or assembler. Data space is the space required to store the constants and variables of your program. Stack space is the space required for function calls — return addresses, the parameters passed to the function, and local variables. These three still matter, and wherever required we will discuss space efficiency, but compared with space, time is the real worry.

1.7.3 Time Efficiency and the Word "Fast"

Time efficiency is, in general terms, how fast a given algorithm executes. But "fast" is an abstract word — what does fast mean? That question is the thread of the whole course. Student answers captured the angles we will develop:

• the time it takes to execute;
• a relative concept — whichever algorithm takes less time is more time-efficient;
• iterations should be minimum;
• time as a function of the input;
• an algorithm can have a best case and a worst case of time efficiency;
• the least number of calculations.

All of these points will be discussed properly in the coming sessions. Notice what the answers already contain: "function of the input" and "best/worst case" point at the analytical model, while "minimum iterations" and "least calculations" hint at counting operations — the two tools that Sections 1.8 to 1.12 build.

1.7.4 What Controls Time Efficiency — and What You Control

The time efficiency of an algorithm depends on several factors:

1. The speed of the computer.
2. The choice of programming language.
3. The compiler used.
4. The choice of algorithm.
5. The size or number of inputs.

Real-world: factors 1 to 3 are mostly outside your control in a job. You are already working in a company; the computer you get is decided by the company, the programming language may be forced on you, and the compiler may be bought once and used across the organization. What you fully control is the choice of algorithm, and partly the size or number of inputs. Given one problem, my algorithm might take 20 seconds while yours takes 2 seconds — that difference comes from the choice of algorithm and the input size. Input size sometimes is not in your control either; how you write the algorithm always is. If you are smart enough, you write a good algorithm, a fast algorithm.

The three exchanges together draw the boundary of the course's analysis: hardware (cores), platforms (browser vs desktop app), and languages (Java vs Python) all influence execution, but the course analyzes the algorithm on paper — before any of those exist. That is why the next sections replace experimental measurement with the analytical model.

Real-world connection: in industry the computer, language, and compiler are fixed by the company, so the two levers a developer actually controls are the algorithm and the input size — exactly the two factors this course trains you to reason about. Choosing a sorting routine that is 10 times faster on the company's data is a 10× win that no hardware purchase can match per unit of effort.

1.8 Experimental Analysis and Its Limitations

1.8.1 The Experimental Approach

The most natural way to measure an algorithm is experimental: implement the algorithm, execute the program on various test inputs, and record the actual time spent. You can do this yourself — for example, write a simple program that multiplies two matrices (a classic case where runtime is visible), run it in Jupyter or any environment you like, and observe the real time taken.

1.8.2 Four Limitations of Experimental Studies

The experimental approach fails on four counts:

1. Implementation is a must. You need to know a programming language, you must implement the algorithm, you need a computer to execute it, and you must know exactly what input and output are expected. Every time you want to check something, that whole setup must happen again.

1. Execution is possible only on a limited set of inputs. You can never try all inputs; you test only what you happen to run. The behavior on the inputs you did not run is simply unknown.

1. Inputs must be representative of real scenarios. Suppose an algorithm is meant for integers in the range 0 to 100, but the experimenter tests only values from 101 to 200 and reports success. The test inputs did not represent the real domain, so the experiment proves nothing. A result about the wrong range of inputs is evidence about the wrong question.

1. Comparing two algorithms requires the same environment. You cannot run one program on one computer, another on a faster computer, and then claim the second is better. The comparison must happen on the same setup, because a speed difference could be a hardware difference in disguise.

These limitations are the reason the course switches to the analytical model — a method that takes all possible inputs into account, needs no program, and compares algorithms independently of any hardware or software environment. That is the model of Section 1.9.

Real-world connection: benchmark testing in industry hits the same four walls — companies benchmark candidate libraries or cloud instances and must control hardware, representative workloads, and identical environments, or the benchmark results mislead the purchase decision. The analytical model avoids these traps by reasoning about the algorithm itself rather than about one execution of it.

1.9 The Analytical Model and Pseudocode

1.9.1 The Analytical Model

The analytical model starts from a high-level description of the algorithm and takes into account all possible inputs. It evaluates the efficiency of an algorithm in a way that is independent of the hardware and software environment. With nothing but pen and paper, you write an algorithm and analyze its efficiency before a single line of code exists.

This directly answers the four limitations of Section 1.8: no implementation is needed (the description is enough), all possible inputs are considered (not a limited test set), representativeness is automatic (every input is in scope), and comparisons are fair (the environment is irrelevant because the analysis does not execute anything).

1.9.2 Pseudocode: A Common Language

If everyone wrote algorithms in their own natural language — Hindi, English, Malayalam, Tamil, whichever — no two people would understand each other. Pseudocode solves that problem: it is a mixture of natural language and high-level programming concepts. It is not a programming language; it uses the widely accepted concepts of high-level programming to describe the main ideas behind an implementation. The expectation is that you write algorithms in pseudocode. Worst case, plain English is acceptable — but it must be universally accepted English that anyone can understand. How to declare methods, how a method returns, and how to write control-flow statements are standard conventions you can read about in the textbook.

The payoff of these conventions: because the same symbols mean the same thing to every reader, an algorithm written in pseudocode can be analyzed by anyone who knows the conventions — which is exactly what the analytical model needs as its input language. When the course later writes algorithms like arrayMax (Section 1.11), every line will use these conventions.

Real-world connection: pseudocode is the shared language of technical interviews and design documents — teams describe an approach in pseudocode before agreeing on the implementation language, so that the algorithm is discussed and analyzed independently of Java, Python, or C++. This course trains exactly that habit.

1.10 The RAM Model and Primitive Operations

1.10.1 Primitive Operations

A primitive operation is a basic computation performed by an algorithm. The working examples are:

• assigning a value to a variable
• calling a method
• performing an arithmetic operation
• indexing into an array
• following an object reference
• returning from a method
• comparing two numbers

This list is not complete, but it covers most of what an algorithm does. The definition is only "basic computations performed by an algorithm" — you understand what counts by looking at the algorithm itself.

1.10.2 The Random Access Machine Model

The analytical model we use is the RAM model — the random access machine model. Two statements carry the whole model:

• Random access means the ability of the CPU to access an arbitrary memory cell with one primitive operation — in one primitive operation.
• The CPU can perform any primitive operation in a constant number of steps, and that constant does not depend on the size of the input. Assigning a value, calling a method, doing an arithmetic operation, indexing into an array — none of these are affected by how big the input is.

When we say a constant number of steps, assume it is one. One, ten, hundred — it does not matter to us, and you will understand why it does not matter. For the moment, accept it as stated; the worked example will make it concrete.

1.10.3 Counting Primitive Operations

The RAM-model approach is simply to count primitive operations. Each primitive operation corresponds to constant time:

$$T(p)=c$$

where $T(p)$ is the time taken by one primitive operation $p$, and $c$ is a constant — one unit, whether that unit is a millisecond, a nanosecond, a second, or an hour. The running time of an algorithm is then a bound on the number of primitive operations it performs: an upper bound on the number of primitive operations is the running time of that algorithm.

Real-world connection: the RAM model is the standard teaching model used in every major algorithms text — it abstracts away caches, parallelism, and word-size limits to make running time a function of the input alone. Its predictions match real machines closely enough to guide engineering choices, which is why this model, and not wall-clock timing, drives the rest of the course.

1.11 Counting Primitive Operations: arrayMax

The model example for RAM-model analysis is the array maximum algorithm. The header: Algorithm arrayMax, input is array $A$ with $n$ elements (and $n$ is the number of elements in the array), output is the maximum element of $A$.

Algorithm arrayMax(A, n)
    currentMax <- A[0]
    for i <- 1 to n-1 do
        if currentMax < A[i] then
            currentMax <- A[i]
    return currentMax

1.11.1 Per-Statement Counts

Going statement by statement:

• Statement 1: currentMax <- A[0] — 2 primitive operations: indexing into the array ($A[0]$) and assigning a value to a variable.
• For-loop header: for i <- 1 to n-1 — the initialization $i\leftarrow 1$ is 1 primitive operation (assignment), and it happens exactly once. The implicit check $i<n$ is 1 primitive operation (comparing two numbers), and this comparison is performed $n$ times — once for $i=1,2,\dots ,n-1$ where it is true, and one final time when it is false and the loop exits.
• If condition: if currentMax < A[i] — 2 primitive operations: a comparison and an indexing into the array.
• Assignment: currentMax <- A[i] — 2 primitive operations: indexing and assignment. This one runs only when the if condition is satisfied.
• Hidden increment: i <- i + 1 — 2 primitive operations: the addition $i+1$ and the assignment. Do not miss this one; it is the statement everyone forgets.
• Return: return currentMax — 1 primitive operation.

The body of the loop executes $n-1$ times, not $n$ times — the extra check is the final false-condition check that lives in the for-loop header itself.

1.11.2 The n vs. n-1 Question

1.11.3 The At-Least Case: 5n

Each iteration of the body contributes either 4 or 6 primitive operations: if the if condition is not satisfied, the iteration costs 2 (comparison + indexing) + 2 (hidden increment) = 4; if it is satisfied, the assignment statement adds 2 more, for 6.

The fastest case for this algorithm is when the if condition is never satisfied — when the largest number is already at $A[0]$, no assignment inside the loop ever fires. Then:

$$T(n)=2+1+n+4(n-1)+1=5n$$

Reading the sum: 2 for the first statement, 1 for the initialization, $n$ for the $n$ comparisons in the for-loop header, $4(n-1)$ for the loop body (4 operations per iteration, $n-1$ iterations), and 1 for the return. Simplifying: $2+1+n+4n-4+1=5n$.

This $5n$ is the at-least time of the algorithm: the algorithm cannot execute in fewer than $5n$ primitive operations. There is no input on which it runs faster.

1.11.4 The At-Most Case: 7n - 2

The slowest case is when the if condition is satisfied on every iteration — for example, when the largest number sits at the very end of the array, so every element is larger than the current maximum. Then each iteration costs 6 primitive operations, and:

$$T(n)=2+1+n+6(n-1)+1=7n-2$$

Again reading the sum: $2+1+n+6(n-1)+1=2+1+n+6n-6+1=7n-2$. This $7n-2$ is the at-most time of the algorithm: no input makes this algorithm take more than $7n-2$ primitive operations.

Between the two bounds: at least $5n$, at most $7n-2$, and the difference comes entirely from how often the if condition fires. Every extra satisfied if condition adds 2 operations (the indexing + assignment inside the if body).

1.11.5 Verdict: Too Slow to Be Practical

After the full count, the honest verdict: is this an effective way to analyze algorithms? No. The RAM model and the primitive-operation count are very time-consuming — the class spent roughly 20 minutes counting five statements. Real programs have hundreds or thousands of lines, so this cannot be the method for every algorithm. A different method is needed: the basic operation method, which is what the course will use from here on.

Real-world connection: the RAM-model count of arrayMax is the textbook example of exact operation counting — every algorithms text works this same problem to show the mechanics of primitive-operation analysis, and it is the stepping stone to the asymptotic analysis used in industry, where $5n$ and $7n-2$ are both reported as "linear time".

1.12 The Basic Operation Method

1.12.1 What Is a Basic Operation?

The basic operation of an algorithm is the operation that contributes most towards the running time of the algorithm. In simple terms, it is the statement that executes the maximum number of times — under the assumption that the statement executed most often also takes the maximum time. These two can differ, but in about 99% of cases they are the same statement. In that remaining 1%, take the operation that contributes most towards the running time.

The correction to keep: a loop contains the basic operation, but a loop is a control structure, not a computation — the basic operation is the statement that executes the maximum number of times inside the algorithm. "A statement inside the loop" is practically close, but "the loop itself" is not the operation.

1.12.2 The 10-Second Argument

Why can we ignore everything except the basic operation? Suppose one statement of an algorithm takes 10 seconds, and all the others take 1, 2, 3, or 4 seconds. We got the major player — the statement that takes 10 seconds. We worry only about the time taken by that operation, because it dominates everything else.

1.12.3 The Three-Step Recipe

The analysis then has three steps:

1. Identify the basic operation of the algorithm.
2. Count the total number of times that operation is executed.
3. Express that count as a function of the input — that function is the time taken.

Conceptually the recipe is complete. We will see next session how the counting itself is done.

1.12.4 The General Plan for Non-Recursive Algorithms

The general plan for analyzing any non-recursive algorithm:

1. Decide on a parameter $n$ indicating the input size.
2. Identify the algorithm's basic operation.
3. Check whether the number of times the basic operation is executed depends only on the input size $n$. If it also depends on the type of input, investigate worst-case, average-case, and best-case efficiency separately.
4. Set up a summation expressing the number of times the algorithm's basic operation is executed.
5. Simplify the summation using standard formulas.

Next session, arrayMax will be analyzed again — this time with the basic operation method, not primitive operations. The pace from here on picks up: this first session was deliberately slow because it is the first, and the recorded lectures should be completed before each class so the live sessions can move faster.

Real-world connection: the basic-operation method is how every performance-sensitive code review works in industry — find the operation that dominates (the one inside the hot loop), count how often it runs as a function of the data size, and optimize that. Improving the dominant operation improves the program; polishing operations that run once changes nothing.

Exam Guidance Summary

Everything below is the distilled, exam-facing summary of this session. Each item maps to a section of the notes where the full reasoning lives.

• Evaluation components: EC1 = 30% (quizzes + assignments), EC2 = mid-semester exam = 30%, EC3 = end-semester exam = 40%. Together they sum to 100%.
• EC1 detail: Quiz 1 = 5%, Quiz 2 = 5% (the two quizzes are averaged, then scaled to 5%), Assignment 1 = 12%, Assignment 2 = 13%. The professor's arithmetic: 25% assignments + 5% quiz average = 30%. (Reconciled: the spoken weightages state Assignment 2 = 13%, matching the 25% combined assignment total of 12 + 13.)
• Quizzes: exactly two per semester, 1 hour each, open for several days (about a week), average of the two taken. Dates and due dates are announced on the portal.
• Mid-semester exam: 30%, 2 hours. Syllabus: contact sessions 1 to 5 — that is, all recorded lecture content plus contact hours up to contact hour 10.
• End-semester exam: 40%, 2.5 hours. Covers all topics in the syllabus, not only post-mid-semester material. The split between pre- and post-mid-semester content adjusts based on mid-semester performance — possibilities mentioned: 60/40, 70/30, 75/25.
• Midnight-call questions: "What is an algorithm?" — a finite sequence of unambiguous step-by-step instructions followed to accomplish a given task — and "What are the properties of an algorithm?" — input, output, finiteness, definiteness, effectiveness. Be ready to answer both at any hour.
• Algorithm verification: expect to check a given algorithm against the definition and all five properties, exactly the way Euclid's algorithm was verified — property by property, each with a reason.
• RAM-model questions: a question of the form "analyze this algorithm using the RAM model" means counting primitive operations per statement — assignment, method call, arithmetic, array indexing, object reference, return, comparison — and producing at-least (best) and at-most (worst) totals like $5n$ and $7n-2$.
• Basic operation method: the five-step plan for non-recursive algorithms (input-size parameter, identify the basic operation, check input-type dependence and split worst/average/best cases, set up the summation, simplify it) is the analysis recipe for the rest of the course.
• Study workflow: complete the recorded lectures before each live session (the in-class revision only skims key points); refer to the merged course version; use the primary textbook first, then CLRS for depth.

Key Industry Applications

How this session's ideas show up in real working environments:

• Real-world: in industry, the computer, the programming language, and the compiler are usually fixed by the company, so efficiency gains come from the choice of algorithm and how you write it — the two factors you control.
• Real-world: cloud storage makes space efficiency a secondary concern; even without a large machine, you can rent the storage you need, so program space, data space, and stack space matter less than time.
• Real-world: experimental timing is done by implementing the algorithm — a matrix multiplication program run in Jupyter or any environment you know gives actual wall-clock numbers, which is exactly the experimental analysis the course replaces with the analytical model.
• Real-world: outputs need not appear on a screen — sending an email, initiating a phone call, or escalating a problem are all legitimate outputs of an algorithm.
• Real-world: Java and Python both appear as implementation targets; the same reference textbook ships in both languages, so you can implement your designed algorithms in whichever you know.
• Seed for later: Euclid's algorithm is the standard method for computing the greatest common divisor, and it is the running example of a properly specified, verifiable algorithm — it will return later when the course analyzes algorithms more formally.