Unit 3 – Compression

Computational Innovation Task | Unit 4 – Data 


Daily Lesson Plans 

This material contains a comprehensive collection of 90-minute lesson plans for a semester’s worth of instruction in AP Computer Science Principles to serve as a companion to this textbook. Each lesson plan includes clear objectives, related requirements, a list of necessary materials, a detailed procedure, an assessment method, and a reflection section. The lessons are designed to be engaging and interactive, incorporating a variety of teaching techniques to help students understand and apply the key concepts of computer science. In order to modify the course for a year-long course with approximately 180 instruction days, each lesson plan can easily be spread across two days of instruction. 

Explore Lesson Plans

Textbook 

Computer Science Principles: The Foundational Concepts of Computer Science, 5th Edition, Kevin Hare – Yellow Dart Publishing – 2024

Explore the Book

Daily Practice Questions

Enjoy complimentary access to a daily selection of 5 random questions from our extensive pool of over 500 thoughtfully crafted questions – even if you’re not a member. Dive into the excitement of learning with these free, rotating questions that change every 24 hours, offering a taste of the variety and depth our content and book have to offer.

Today’s Questions

Lessons:

Unit Duration:

  • 7.5 hours | 5 class periods (90-minutes)

Project, Test, and Quiz Resources:

Lesson 15 | 3.0 – Encoding/Compression 

Lesson Objectives: 

  • To understand the concept of encoding and compressing information on a computer
  • To distinguish between lossy and lossless compression techniques 
  • To compare and contrast variable and fixed length encoding 
  • To explain the working of Huffman trees 
  • To create a small two-color image and encode it, then use run-length encoding to compress the image 
  • To calculate the amount of compression achieved 

Related Requirements: 

  • Basic knowledge of computer systems and data representation 

Lesson Materials: 

Lesson Procedure: 

  1. 1. Introduction (10 minutes) 
    • Start the lesson by asking students if they have ever encountered a file that was too big to be sent over email or stored on their computer. 
    • Ask students to suggest ways they could reduce the size of the file. 
    • Introduce the topic of encoding and compressing information on a computer, and explain that this is the focus of today’s lesson. 
  2. Understanding Encoding and Compression (20 minutes) 
    • Define encoding and compression and explain the purpose of each. 
    • Discuss lossy and lossless compression techniques, including their advantages and disadvantages. 
    • Compare and contrast variable and fixed length encoding. 
  3. Huffman Trees (20 minutes) 
    • Play the video How Computers Compress Text to introduce students to Huffman Trees. 
    • Discuss the working of Huffman trees and their use in compressing data. 
  4. Activity (30 minutes) 
    • Have students work in pairs or small groups to complete the following activity:
    • Use an online pattern creator website to create a small two-color image.
    • Encode the data of the image. 
    • Use run-length encoding to compress the image. 
    • Calculate the amount of compression achieved. 
  5. Assessment (10 minutes) 
    • Ask students to present their observations and results from the activity to the class. 
    • Evaluate their understanding of encoding, compression, lossy vs. lossless compression techniques, variable vs. fixed length encoding, and Huffman trees. 
  6. Lesson Reflection (10 minutes) 
    • Ask students to reflect on what they learned during the lesson, what they found challenging, and what they would like to learn more about in the future. 
    • Encourage them to ask questions and provide feedback on the lesson. 

Assessment Method: 

  • Class participation and presentation 
  • Completion of the worksheet 
  • Observation during the activity 

Mapped Standards:

College Board AP Computer Science Principles (CSP) Framework:
  • DAT-2.C.1 The ability to process data depends on the capabilities of the users and their tools. Therefore, a data set can be considered to be a large data set based on the capabilities of some users, but not necessarily for all users.
  • DAT-2.C.2 Data pose challenges regardless of size. Such as: the need to clean data; incomplete data; invalid data; or the need to combine data sources.
  • DAT-2.C.3 Depending on how data are being collected, the data may not be uniform. For example, if users enter data into an open field, the way they choose to abbreviate, spell or capitalize something may vary from user to user.
  • DAT-2.C.4 Cleaning data is a process that makes the data uniform without changing its meaning. For example, replacing all abbreviations, spellings and capitalizations with the same word.
  • DAT-1.D.1 Data compression can reduce the size (number of bits) of the data transmitted or stored.
  • DAT-1.D.2 Fewer bits does not necessarily mean less information.
  • DAT-1.D.3 The amount of reduction in bits by compression depends on both the amount of redundancy in the original data representation and the compression algorithm applied.
  • DAT-1.D.4 Lossless data compression algorithms can usually reduce the number of bits stored or transmitted while guaranteeing complete reconstruction of the original data.
  • DAT-1.D.5 Lossy data compression algorithms can significantly reduce the number of bits stored or transmitted, but only allow the reconstruction of an approximation of the original data.
  • DAT-1.D.6 Lossy data compression algorithms can usually reduce the number of bits stored or transmitted more than lossless compression.
  • DAT-1.D.7 In situations where quality or ability to reconstruct the original is maximally important, lossless compression algorithms are typically chosen.
  • DAT-1.D.8 In situations where minimizing data size or short transmission time is maximally important, lossy compression algorithms are typically chosen.
CSTA Standards:
  • 3B-DA-06: Analyze the trade-offs between various compression techniques, considering factors like data integrity and compression ratio.

Lesson 16 | 3.1 – Text Compression 

Lesson Objectives: 

  • To review the concepts of encoding and compression, run-length encoding, and Huffman trees 
  • To introduce the LZ77 compression technique and its implementation
  • To understand the use of dictionaries in different compression techniques
  • To engage in an activity that applies the concepts learned in class 

Related Requirements: 

  • Familiarity with encoding and compression techniques 

Lesson Materials: 

Lesson Procedure: 

  1. Introduction (10 minutes): 
    • Review the concepts of encoding and compression, run-length encoding, and Huffman trees
    • Introduce the LZ77 compression technique and its significance 
  2. Video Presentation (15 minutes): 
    • Watch the video Elegant Compression in Text (The LZ 77 Method) 
    • Ask students to take notes on the key concepts and how LZ77 works 
  3. Discussion and Explanation (15 minutes): 
    • Go over the key concepts from the video and answer any questions the students may have 
    • Explain the use of dictionaries in different compression techniques 
  4. Activity (40 minutes): 
    • Students will use an online text compression widget to compress popular song lyrics using the “shorter symbol” compression technique 
    • Students will work in pairs and compare the results of their compression with other groups 
    • Students will discuss the results and explain why some song lyrics compress better than others 

Lesson Reflection: 

  • After the class, students will reflect on what they learned and what they found challenging 
  • Students will also discuss ways to improve their understanding of the concepts covered in the class. 

Mapped Standards:

College Board AP Computer Science Principles (CSP) Framework:
  • CRD-1.C.1 Effective collaborative teams practice interpersonal skills including but not limited to: communication skills; consensus building; conflict resolution; negotiation.
  • DAT-2.C.5 Problems of bias are often caused by the type or source of data that is being collected. Bias is not eliminated by simply collecting more data.
  • DAT-1.D.1 Data compression can reduce the size (number of bits) of the data transmitted or stored.
  • DAT-1.D.2 Fewer bits does not necessarily mean less information.
  • DAT-1.D.3 The amount of reduction in bits by compression depends on both the amount of redundancy in the original data representation and the compression algorithm applied.
  • DAT-1.D.4 Lossless data compression algorithms can usually reduce the number of bits stored or transmitted while guaranteeing complete reconstruction of the original data.
  • DAT-1.D.5 Lossy data compression algorithms can significantly reduce the number of bits stored or transmitted, but only allow the reconstruction of an approximation of the original data.
  • DAT-1.D.6 Lossy data compression algorithms can usually reduce the number of bits stored or transmitted more than lossless compression.
  • DAT-1.D.7 In situations where quality or ability to reconstruct the original is maximally important, lossless compression algorithms are typically chosen.
  • DAT-1.D.8 In situations where minimizing data size or short transmission time is maximally important, lossy compression algorithms are typically chosen.
CSTA Standards:
  • 2-DA-09: Utilize and evaluate different data representations and compression techniques to analyze their impacts on data utility and storage efficiency.

Lesson 17 | 3.2 – Audio/Video Compression 

Lesson Objectives: 

  • To define and understand the terms sample rate, bit depth, bit rate, temporal compression and spatial compression 
  • To identify the different file types and their method of compression 
  • To observe the impact of compression on audio and video quality 

Related Requirements: 

  • Basic understanding of audio and video technology 
  • Familiarity with the use of video and audio file types 

Lesson Materials: 

Lesson Procedure: 

  1. Introduction (15 minutes) 
    • Brief overview of the topic and the purpose of the lesson 
    • Introduction of the terms sample rate, bit depth, bit rate, temporal compression, and spatial compression 
    • Ask the students if they have encountered any audio or video problems related to compression. 
  2. Video Activity (15 minutes) 
    • Play the video: How Image Compression Works, Why Snow and Confetti Ruin YouTube Video Quality 
    • Ask students to focus on the examples of compression and its impact on video quality 
    • Discuss their observations as a class. 
  3. Audio Activity (15 minutes) 
    • Play the audio clip of the human audio spectrum 
    • Ask students if they can hear the extreme ends and how the quality of the audio changes 
    • Discuss as a class the impact of compression on audio quality 
  4. Jigsaw Activity (30 minutes) 
    • Distribute the Jigsaw Activity Sheet to the students 
    • Divide the class into small groups of 4-5 students 
    • Each group will research one of the 10 popular file types and their method of compression 
    • After 30 minutes, the groups will split off into new groups and will share their findings with their new group (one expert for each file type in the new groups)
    • The class will complete the Jigsaw Activity Sheet in their new groups 5. Assessment (15 minutes) 
    • Discussion on how audio and video compression can impact the quality of the final product 

Lesson Reflection: 

  • Ask students what they learned from the lesson and what was challenging for them
  • Solicit suggestions for improving the lesson for future classes 
  • Reflect on the effectiveness of the lesson activities and make any necessary adjustments for future classes. 

Assessment Method: 

  • Class discussion 
  • Completion of Jigsaw Activity Sheet

Mapped Standards:

College Board AP Computer Science Principles (CSP) Framework:
  • CRD-1.C.1 Effective collaborative teams practice interpersonal skills including but not limited to: communication skills; consensus building; conflict resolution; negotiation.
  • DAT-2.C.1 The ability to process data depends on the capabilities of the users and their tools. Therefore, a data set can be considered to be a large data set based on the capabilities of some users, but not necessarily for all users.
  • DAT-2.C.2 Data pose challenges regardless of size. Such as: the need to clean data; incomplete data; invalid data; or the need to combine data sources.
  • DAT-2.C.3 Depending on how data are being collected, the data may not be uniform. For example, if users enter data into an open field, the way they choose to abbreviate, spell or capitalize something may vary from user to user.
  • DAT-2.C.6 The size of the data set affects the amount of information that can be extracted from it.
  • DAT-2.C.8 Scalability of systems is an important consideration when working with large data sets, since the size or scale of a system affects how that data set can be processed and stored.
  • DAT-1.D.1 Data compression can reduce the size (number of bits) of the data transmitted or stored.
  • DAT-1.D.2 Fewer bits does not necessarily mean less information.
  • DAT-1.D.3 The amount of reduction in bits by compression depends on both the amount of redundancy in the original data representation and the compression algorithm applied.
  • DAT-1.D.4 Lossless data compression algorithms can usually reduce the number of bits stored or transmitted while guaranteeing complete reconstruction of the original data.
  • DAT-1.D.5 Lossy data compression algorithms can significantly reduce the number of bits stored or transmitted, but only allow the reconstruction of an approximation of the original data.
  • DAT-1.D.6 Lossy data compression algorithms can usually reduce the number of bits stored or transmitted more than lossless compression.
  • DAT-1.D.7 In situations where quality or ability to reconstruct the original is maximally important, lossless compression algorithms are typically chosen.
  • DAT-1.D.8 In situations where minimizing data size or short transmission time is maximally important, lossy compression algorithms are typically chosen.
CSTA Standards:
  • 2-CS-01: Analyze and compare different data compression methods to assess their suitability for audio and video data.

Lesson 18 | 3.3 – New File Type 

Lesson Objectives: 

  • To review the various compression techniques covered in this unit, including lossless and lossy compression. 
  • To understand the process of creating a compression algorithm using multiple compression techniques. 
  • To apply the knowledge of compression techniques to create a lossless file type for two-color images. 
  • To analyze the results of the algorithm and present the findings in a clear and concise manner. 

Related Requirements: 

  • Knowledge of data compression techniques, including lossless and lossy compression.
  • Understanding of image file formats and their compression methods.
  • Basic skills in creating and manipulating images using a graphics editor.
  • Ability to work in a team and collaborate effectively. 

Lesson Materials: 

Lesson Procedure: 

  1. 1Introduction (15 minutes): 
    • Review the compression techniques covered in the previous lessons (e.g. run-length encoding, Huffman coding, etc.). 
    • Highlight the difference between lossless and lossy compression and the advantages and disadvantages of each. 
    • Briefly discuss the importance of compression in data storage and transmission.
  2. Group Activity (60 minutes): 
    • Divide the class into groups of 3-4 students. 
    • Distribute the digital handout with the instructions and rubric for the activity.
    • Provide time for students to brainstorm and discuss their ideas for the algorithm.
    • Monitor the progress of the groups and provide guidance and support as needed.
    • Encourage students to share their findings with the class and ask questions.
  3. Presentation (15 minutes): 
    • Have each group present their algorithm and its results. 
    • Encourage questions and discussions among the groups. 

Assessment Method: 

  • Group activity (60%) – based on the quality of the algorithm, the clarity of the explanation, and the accuracy of the results.
  • Presentation (20%) – based on the quality of the presentation, including the organization, clarity, and engagement of the group. 
  • Reflection (20%) – based on the student’s reflection on their learning experience, including the strengths and weaknesses of the algorithm, what they learned, and what they would do differently next time. 

Lesson Reflection: 

  • After the lesson, have students reflect on their learning experience by answering the following questions: 
    • What was the most challenging part of creating the algorithm? 
    • What did you learn about compression techniques and the process of creating a compression algorithm? 
    • What would you do differently next time? 
  • Collect and review the reflections to assess the effectiveness of the lesson and identify areas for improvement. 

Mapped Standards:

College Board AP Computer Science Principles (CSP) Framework:
  • CRD-1.C.1 Effective collaborative teams practice interpersonal skills including but not limited to: communication skills; consensus building; conflict resolution; negotiation.
  • DAT-2.A.1 Information is the collection of facts and patterns extracted from data.
  • DAT-2.C.1 The ability to process data depends on the capabilities of the users and their tools. Therefore, a data set can be considered to be a large data set based on the capabilities of some users, but not necessarily for all users.
  • DAT-2.C.7 Large data sets are difficult to process using a single computer and may require parallel systems.
CSTA Standards:
  • 3A-AP-14: Develop and simulate a model of a new compression algorithm, evaluating its effectiveness and efficiency.

Lesson 19 | Unit 3 Exam 

Lesson Objectives: 

  • To understand the concepts of encoding, compression, and file types
  • To be able to apply the knowledge of encoding, compression, and file types in practical scenarios 
  • To be able to analyze and evaluate the effectiveness of different encoding and compression techniques and file types 

Related Requirements: 

  • Basic understanding of computer systems and data storage 
  • Knowledge of different data formats and file types 

Lesson Materials: 

  • Encoding, Compression, and File Types Exam 
  • Computer Science Principles, Chapter 4 
  • Blown to Bits, Chapters 2-3 
  • 9 Algorithms that Changed the Future, Chapter 8 

Lesson Procedure: 

  1. Introduction (5 minutes): 
    • The teacher will explain the objectives of the class and provide a brief overview of the concepts of encoding, compression, and file types 
  2. Exam (50 minutes): 
    • The teacher will distribute the Encoding, Compression, and File Types Exam to the students
    • The students will complete the exam independently 
  3. Reading (35 minutes): 
    • If the students finish the exam early, they will start reading the assigned chapters from the three books 
  4. The teacher will provide a brief overview of the next unit on data, spreadsheets, and databases 

Assessment Method: 

  • Encoding, Compression, and File Types Exam 
  • Quizzes and discussions based on the readings 
  • Group or individual projects to apply the concepts in practical scenarios 

Lesson Reflection: 

  • The teacher will reflect on the effectiveness of the lesson in achieving the objectives
  • The teacher will seek feedback from the students on the exam and the readings
  • The teacher will make any necessary changes to the lesson plan based on the reflection and feedback for future classes. 

Mapped Standards:

College Board AP Computer Science Principles (CSP) Framework:
  • AAP-2.A.1 An algorithm is a finite set of instructions that accomplish a specific task.
  • CRD-1.C.1 Effective collaborative teams practice interpersonal skills including but not limited to: communication skills; consensus building; conflict resolution; negotiation.
  • CRD-2.A.2 An understanding of the purpose of a computing innovation provides developers with an improved ability to develop the computing innovation.
  • DAT-2.A.3 Digitally processed data may show correlation between variables. A correlation found in data does not necessarily imply a causal relationship exists. Often additional research is needed to understand the exact nature of the relationship.
CSTA Standards:
  • 3B-DA-07: Assess knowledge of encoding and compression through structured exam scenarios, focusing on practical applications and theoretical understanding.

Computational Innovation Task | Unit 4 – Data 

Membership

For those hungry for more, our membership unlocks the full spectrum of over 500 questions, providing a comprehensive exploration of the diverse topics covered in our content and book. Delve deeper into the world of computer science, enhance your understanding, and master the principles that matter. Our membership also grants you exclusive access to detailed units from the comprehensive book and on our website. From foundational concepts to advanced topics, our units offer invaluable resources to support your learning journey. Elevate your exploration of computer science and make the most of your membership!

Ready to take the plunge into the world of computer science? Start Your Membership Today and enjoy free daily questions along with a treasure trove of over 500 more!

Explore Membership

Subscribe to our Newsletter

AP Computer Science Principles/Teacher Certification Prep Course

AP Computer Science Principles/Teacher Certification Prep Course

Get full access to:

  • Comprehensive explanations of the concepts
  • 500+ Practice multiple choice questions
  • Customizable Test Generator
  • 90+ Curated videos
  • 15 Projects, Tests, and Quizzes (includes all à la carte items)
  • 12 Units of materials
  • Built-in Block-to-JavaScript practice tool
  • All future resources and questions for life!
$19.99
Shop now

Computational Innovation Task | Unit 4 – Data