Problem Solving with Algorithms and Data Structures using Python – Free Book (BSCS)

BSCS, BSIT and BSSE students can read the complete Data Structures and Algorithms textbook “Problem Solving with Algorithms and Data Structures using Python” by Bradley N. Miller, David L. Ranum and Roman Yasinovskyy, published free online by Runestone Academy. It covers the full Data Structures and Algorithms course taught at Pakistani universities.

This is an interactive book rather than a static file: every code example runs inside the page, and each chapter ends with a Summary and a Key Terms list. Eight chapters take you from Big O analysis through stacks, queues and linked lists to recursion, searching and sorting, trees, heaps and graph algorithms — which is the exact spread of topics a university DSA paper is built from.

Book Overview

Course	Data Structures & Algorithms
Level	University / BSCS
Edition	Interactive Edition (3rd Edition also linked below)
Authors	Bradley N. Miller, David L. Ranum, Roman Yasinovskyy
Publisher	Runestone Academy
Language	English
Total Chapters	8
License	Interactive Edition © Franklin Beedle & Associates; 3rd Edition CC BY-NC-SA 4.0
Format	Interactive HTML with runnable code (free to read)

Chapter List

Chapter 1: Introduction

Difficulty: Easy · Key topics: abstraction, abstract data types, Python review, defining classes

The opening chapter sets up the way the rest of the book thinks. It explains what computer science actually studies, why abstraction matters, and separates an abstract data type — what a structure does — from its implementation, which is how it does it. The second half is a full Python refresher: the built-in collections, input and output, control structures, exception handling, defining functions, and finally defining classes, including inheritance hierarchies. Forty key terms are listed at the end, and they are the vocabulary the remaining seven chapters assume.

Key Points:

• An abstract data type describes what a structure does; the implementation describes how — keeping them apart is information hiding.
• Python’s sequential collections are lists, tuples and strings; dictionaries and sets are non-sequential.
• Classes give a concrete implementation of an ADT, and existing methods can be overridden.
• A child class must call its parent’s constructor before setting up its own data.
• Exception handling lets a program deal with a failed operation instead of stopping.
• Key terms here include abstraction, encapsulation, interface, mutability, and shallow versus deep equality.

Practice Tip: Run the Python review sections inside the page. The interactive edition executes code in the browser, so refreshing loops, list comprehensions and classes here is quicker than opening an editor.

Common Mistake: Skipping this chapter because it looks like revision. The ADT vocabulary introduced here — interface versus implementation, shallow versus deep equality — is used without explanation from Chapter 2 onwards.

Important Questions:

• What is an abstract data type? A logical description of what a data structure does and what operations it supports, independent of how those operations are implemented in code.
• What is the difference between an interface and an implementation? The interface is the set of operations a user of the structure can call; the implementation is the code and storage that make those operations work.

Chapter 2: Algorithm Analysis

Difficulty: Medium · Key topics: Big O notation, order of magnitude, performance of Python lists and dictionaries

This chapter answers a question students meet in every later chapter: how do you compare two algorithms without depending on the machine they run on? Execution time is expressed as a step count T(n), and Big O keeps only the term that grows fastest. The standard family of order-of-magnitude functions is introduced, an anagram detection problem is solved four different ways to compare their orders, and the chapter closes by measuring Python’s own list and dictionary operations — results worth memorising because they explain why some programs slow down as data grows.

Key Points:

• Big O keeps the dominant term only: T(n) = 3n² + 2n + 4 is O(n²).
• The order-of-magnitude family: O(1), O(log n), O(n), O(n log n), O(n²), O(n³), O(2ⁿ).
• Python lists: index, index assignment, append and pop() are O(1); pop(i), insert(i, item), del and in are O(n).
• pop() from the end is constant time, but pop(0) is linear because every later element has to shift.
• Python dictionaries: get, set, delete and in are O(1) on average, while copy and iteration are O(n).
• Sorting a list is O(n log n); slicing costs O(k) to read and O(n) to delete.

Memory Tip: Carry one contrast into the exam: membership testing is O(n) in a list and O(1) in a dictionary. The chapter measures it — dictionaries came out thousands of times faster on large data.

Common Mistake: Using a list for repeated membership checks. The answer is the same, but each check costs linear time instead of constant time.

Important Questions:

• What does Big O notation measure? The order of magnitude of an algorithm’s running time as the problem size grows, ignoring constants and lower-order terms.
• Why is a membership test faster in a dictionary than in a list? A dictionary uses hashing to jump straight to the slot, which is O(1) on average, while a list has to scan its elements, which is O(n).

Chapter 3: Basic Data Structures

Difficulty: Medium · Key topics: stacks, queues, deques, linked lists, postfix expressions

Linear structures are defined by where items are added and removed, and this chapter builds four of them as abstract data types before implementing each in Python. The stack section applies LIFO order to balanced parentheses, decimal-to-binary conversion and infix-to-postfix conversion and evaluation. The queue section applies FIFO order to two simulations — hot potato and a printing-task queue that answers how long the average job waits. Deques allow both ends, giving a clean palindrome checker, and the chapter ends with unordered and ordered lists implemented as linked lists of nodes and references.

Key Points:

• A stack is Last In First Out with push, pop and is_empty; a queue is First In First Out with enqueue, dequeue and is_empty.
• A deque allows insertion and removal at both ends: add_front, add_rear, remove_front, remove_rear.
• Stacks are the tool for balanced-symbol checking, base conversion, and infix to postfix conversion and evaluation.
• Queue simulations use random numbers to answer practical questions, such as average waiting time for printing tasks.
• A linked list keeps items in logical order through references, so it does not need contiguous storage.
• Each node holds a data field and a reference to the next node; the head is the special case in every operation.

Practice Tip: Implement the Stack class once and reuse it. The balanced-parentheses, base-conversion and postfix sections are the same three operations wrapped in different loops, so writing the class properly pays for itself three times.

Common Mistake: Forgetting the head when writing linked-list code. Adding or removing at the front is the case that breaks most student implementations.

Important Questions:

• What is the difference between a stack and a queue? A stack removes the most recently added item (LIFO); a queue removes the item that has been waiting longest (FIFO).
• Why does a linked list not need contiguous memory? Because each node stores a reference to the next node, so the order is logical rather than physical and the nodes can sit anywhere.

Chapter 4: Recursion

Difficulty: Hard · Key topics: the three laws of recursion, stack frames, Tower of Hanoi, dynamic programming

Recursion is introduced by summing a list of numbers, then formalised into three laws. The chapter shows how the call stack — the same stack frames that produce a traceback — actually implements recursion, and applies it to converting integers to any base, drawing the Sierpinski triangle, solving the Tower of Hanoi and exploring a maze. The last section is the important one for exams: the coin-change problem, where a greedy choice gives the wrong answer and plain recursion repeats work, which is what dynamic programming fixes by storing results.

Key Points:

• Law 1: a recursive algorithm must have a base case.
• Law 2: it must change its state and move toward the base case.
• Law 3: it must call itself recursively.
• Recursion is implemented with stack frames, so each call keeps its own parameters and return address.
• A recursive solution often mirrors the mathematical definition of a problem, but it can cost more than an iterative one.
• Dynamic programming stores solutions to subproblems so the same work is never repeated.

Memory Tip: The three laws are a checklist you can run in seconds — base case? moving toward it? calling itself? If any answer is no, the function is wrong.

Common Mistake: Assuming a greedy choice always gives the best answer. The coin-change section shows the greedy method failing on certain coin sets, which is exactly why dynamic programming is introduced.

Important Questions:

• What are the three laws of recursion? A recursive algorithm must have a base case, must change its state and move toward the base case, and must call itself recursively.
• What is dynamic programming and why is it used? A technique that stores the results of subproblems and reuses them, so a recursive solution does not solve the same subproblem again and again.

Chapter 5: Searching and Sorting

Difficulty: Hard · Key topics: sequential and binary search, hashing, five sorting algorithms and their complexities

Searching comes first: the sequential search on any list, the binary search on an ordered list, and hashing, which aims at constant-time lookup by computing a slot from the key. Collisions and their solutions — chaining, linear probing, quadratic probing and rehashing — are covered along with the load factor that decides how often collisions happen. The sorting half works through bubble, selection, insertion, shell, merge and quicksort, giving the complexity of each and, for quicksort, showing how a poor pivot damages it. This is the chapter most university DSA papers draw from.

Key Points:

• Sequential search is O(n), on ordered and unordered lists alike.
• Binary search of an ordered list is O(log n) in the worst case.
• Hashing gives constant-time search on average; a hash function maps a key to a slot in the hash table.
• Collisions are resolved by chaining, linear probing or quadratic probing; the load factor is items divided by slots.
• Bubble, selection and insertion sort are all O(n²); shell sort improves on insertion sort and lies between O(n) and O(n²).
• Merge sort is O(n log n) but needs extra space; quicksort is O(n log n) on average, O(n²) with bad pivots, and needs no extra space.

Memory Tip: One verb per sort — bubble compares neighbours, selection picks the smallest, insertion shifts into place, merge splits and rejoins, quicksort partitions around a pivot. Almost every “differentiate between” question rests on those five verbs.

Common Mistake: Quoting quicksort as always O(n log n). A poor pivot drops it to O(n²), which is why the median-of-three pivot method exists.

Important Questions:

• Which sorting algorithms are O(n²) and which are O(n log n)? Bubble, selection and insertion sort are O(n²); merge sort and quicksort (on average) are O(n log n), with shell sort in between.
• What is a collision in hashing and how is it resolved? A collision is when two keys hash to the same slot; it is resolved by chaining the items at that slot or by open addressing methods such as linear or quadratic probing.

Chapter 6: Trees and Tree Algorithms

Difficulty: Hard · Key topics: tree vocabulary, parse trees, traversals, binary heaps, binary search trees, AVL trees

The chapter starts with vocabulary — root, edge, parent, child, sibling, leaf, level, height, subtree — then gives two implementations, a list of lists and nodes with references. A parse tree turns an arithmetic expression into a structure that can be evaluated by traversal, which introduces preorder, inorder and postorder. The second half covers the binary heap, which implements a priority queue in O(log n), then binary search trees, their analysis, and finally AVL trees, which keep the tree balanced with the balance factor and rotations so search stays logarithmic.

Key Points:

• Core vocabulary: root, edge, parent, child, sibling, leaf node, level, height, path, subtree.
• A binary tree can be stored as a list of lists or as nodes holding references to left and right children.
• A parse tree represents an expression so it can be evaluated by traversing the tree.
• Preorder, inorder and postorder differ only in when the root is visited; inorder on a binary search tree returns the values in order.
• A binary heap keeps the heap-order property and implements a priority queue, with insert and delete in O(log n).
• The BST property puts smaller keys on the left and larger keys on the right; an AVL tree keeps it balanced using balance factors and rotations.

Memory Tip: The map ADT is implemented three ways across this book — hashing, binary search tree, AVL tree. If the question is “which is better”, answer with the worst case: hashing O(1) average, an unbalanced BST O(n), an AVL tree O(log n) guaranteed.

Common Mistake: Assuming a binary search tree is automatically fast. Inserting already-sorted data turns it into a chain and search degrades to O(n) — the problem AVL rotations exist to solve.

Important Questions:

• What is the BST property? Every key in the left subtree is smaller than its parent and every key in the right subtree is larger, which is what makes ordered search possible.
• What is the difference between a binary heap and a binary search tree? A heap keeps only the heap-order property between parent and children and is used for priority queues; a BST keeps a full left-right ordering and is used for searching.

Chapter 7: Graphs and Graph Algorithms

Difficulty: Hard · Key topics: adjacency matrix and list, BFS, DFS, topological sort, Dijkstra, Prim

Graphs are defined through vertices, edges, weights and paths, with directed graphs, cycles and acyclic graphs named precisely. Two representations are compared: the adjacency matrix, which is simple but mostly empty on sparse graphs, and the adjacency list, which stores only the edges that exist. The algorithms then arrive through problems — the word ladder for breadth-first search, the knight’s tour for depth-first search — followed by topological sorting for dependent tasks, strongly connected components, Dijkstra’s algorithm for weighted shortest paths and Prim’s algorithm for a minimum spanning tree.

Key Points:

• A graph is a set of vertices joined by edges; edges may carry weights and may be directed (a digraph).
• An adjacency matrix is easy to read but wastes space on sparse graphs; an adjacency list stores only existing edges.
• Breadth-first search uses a queue and finds the shortest path in an unweighted graph.
• Depth-first search follows one branch as deep as it goes and builds a depth-first forest.
• Dijkstra’s algorithm finds shortest paths when edges have weights, using a priority queue.
• Topological sort orders dependent tasks, and Prim’s algorithm builds a minimum spanning tree for broadcasting.

Memory Tip: Pair each search with its structure and its job — queue, BFS, shortest path in an unweighted graph; stack or recursion, DFS, go deep. Add weights and the answer becomes Dijkstra; ask for the cheapest connecting tree and it becomes Prim.

Common Mistake: Using breadth-first search on a weighted graph. BFS counts edges, not weights, so the path it returns is the one with fewest edges, not the cheapest — that is Dijkstra’s job.

Important Questions:

• What is the difference between an adjacency matrix and an adjacency list? A matrix stores a cell for every possible pair of vertices, which is wasteful when few edges exist; a list stores, for each vertex, only the vertices it is actually connected to.
• Which algorithm finds the shortest path in a weighted graph? Dijkstra’s algorithm, which uses a priority queue to always expand the cheapest known path first.

Chapter 8: Advanced Topics

Difficulty: Medium · Key topics: amortized analysis, skip lists, octrees, pattern matching with DFA and KMP

The closing chapter revisits earlier structures at a deeper level. Python lists are examined again through amortized analysis, which explains why append behaves as constant time even though the underlying array is occasionally resized. Recursion returns for a harder set of problems, dictionaries return as skip lists, and trees return as octrees used to reduce the number of colours in an image. The last section is string pattern matching: the simple approach, a deterministic finite automaton, and the Knuth-Morris-Pratt algorithm, compared on how easy each is to build and to use.

Key Points:

• Amortized analysis explains why appending to a Python list counts as constant time on average.
• A skip list is a linked list with extra express levels, giving expected O(log n) search.
• An octree reduces the colour palette of an image, which is how image quantization is made practical.
• Simple brute-force pattern matching is too slow for real text processing.
• A DFA graph matches patterns easily but is complex to construct; the KMP algorithm is easier to build and still fast.
• Key terms here include amortized analysis, skip list, octree, quantization, DFA, KMP and public key encryption.

Practice Tip: Treat this chapter as optional depth chosen by your course — read the skip list section if your outline covers advanced dictionary implementations, and the KMP section if it covers string matching.

Important Questions:

• What is a skip list? A linked list with additional levels of forward references that let a search skip ahead, giving expected O(log n) search time.
• Why is the KMP algorithm preferred over a DFA graph for pattern matching? Both match quickly, but the KMP graph is much simpler to construct, so it is easier to use in practice.

---

Read Problem Solving with Algorithms and Data Structures using Python – Free

This book is free from its official source. There is no official PDF — it is an interactive book, so the code examples run inside the page as you read.

→ Read Interactive Edition

Earlier edition: the 3rd edition is still followed by some course outlines and is the version released under a Creative Commons licence.

→ Read 3rd Edition (CC BY-NC-SA)

We link to the official free copy so you always get the latest, complete and safe version.

---

How to Study This Book

Run the code, do not just read it. Every example is editable and executable inside the page, so change a value and re-run it before moving on. That is the whole advantage this book has over a printed one.

Chapter 1 is Python revision. Skim it if your Python is solid, but do not skip the abstract data type sections — the interface-versus-implementation idea is used constantly afterwards.

Chapters 2, 3 and 5 carry the paper. Big O analysis, stacks, queues and linked lists, and searching and sorting are where most university DSA questions come from. Give them the most time.

Do Chapter 4 before Chapter 6. Tree traversals and heap operations are written recursively, so recursion has to be comfortable first.

Chapter 7 is the heaviest. Graphs bring their own vocabulary plus five algorithms; plan about a week and learn the vocabulary section before touching the algorithms.

Revise from the Summary and Key Terms pages. Every chapter ends with both, and together they are the fastest revision path the day before a paper.

---

Used In These Programs

This book is used for the Data Structures and Algorithms course in BSCS, BSIT and BSSE programs. Browse all Data Structures books, everything tagged Python or BSCS, or the full Computer Science books section.

Who Should Read This

Written for students taking Data Structures and Algorithms after a first programming course. Basic Python is assumed — loops, functions and lists — and Chapter 1 refreshes the rest, so anyone who has finished an introductory Python book can start here. It suits students whose course teaches DSA in Python rather than C++, and anyone who learns better by running and modifying code than by reading pseudocode.

---

Applicable Universities

This book is used at Pakistani universities offering BSCS, BSIT and BSSE, including Punjab University, Virtual University, COMSATS, FAST, UET and other HEC-recognized institutions, wherever the Data Structures course is taught in Python.

FAQs

Related Books

• Data Structures in C++ PDF Download – Aikman Series BSCS
• Object Oriented Programming Using C++ PDF Download – IT Series BSCS
• Database Management System PDF Download – BSCS University

The strength of this book is that the theory and the code sit in the same place: read the definition, run the implementation, then check yourself against the Summary and Key Terms. Open the book above and start with Chapter 2, or with Chapter 1 if your Python needs refreshing. For more titles from the same semester, visit our Computer Science books section.

Problem Solving with Algorithms and Data Structures using Python by Bradley N. Miller, David L. Ranum and Roman Yasinovskyy, published free online by Runestone Academy. Interactive Edition © 2023 Franklin Beedle & Associates; the 3rd Edition (© 2014 Brad Miller, David Ranum) is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 4.0.