Developing a Holistic Understanding of Systems and Algorithms through Research Papers

ABSTRACT

Even though a computer science degree is unavoidably broken into semesters and courses, we always hope that our students form a holistic picture of the discipline by the time they graduate. Yet as educators, we do not have too many opportunities to make this point front and center for an extended period of time. This report es a well-defined portion of this problem: revealing conceptual connections between algorithmic courses (such as Discrete Math, Data Structures, Algorithms) and systems oriented courses (such as Organization, Computer Networks, Operating Systems, and Hardware) through the use of research papers. In particular, we provide a pedagogical framework as well as a set of carefully selected papers to crosscut our disciplinary space in a way that is orthogonal to conventional course design. This framework includes a paper taxonomy, strategies for covering topics that students are yet to encounter in upper level courses, strategies for reading and writing technical papers, three modules (one each for operating systems, networks, and architecture) that can be integrated into standard systems courses, and a new (optional) course template as a container for all of the listed elements. Since we have already tried these ideas once at the institution of the two leading authors, our report is rich with scaffolding suggestions as well.

References

1. A.B.AKahng, J. Lienig, I.L. Markov, and J. Hu. 2011. VLSI Physical Design: From Graph Partitioning to Timing Closure. Springer Netherlands, Amsterdam, Netherlands.
2. Saeed Alaei, Mohammad Ghodsi, and Mohammad Toossi. 2010. Skiptree: A new scalable distributed data structure on multidimensional data supporting range-queries. Computer Communications 33, 1 (2010), 73 -- 82.
3. Lars Arge, David Eppstein, and Michael T. Goodrich. 2005. Skip-webs: Efficient Distributed Data Structures for Multi-dimensional Data Sets. In Proceedings of the Twenty-fourth Annual ACM Symposium on Principles of Distributed Computing (PODC '05). ACM, New York, NY, USA, 69--76.
4. Nikolas Askitis and Justin Zobel. 2009. B-tries for Disk-based String Management. The VLDB Journal 18, 1 (Jan. 2009), 157--179.
5. James Aspnes, Jonathan Kirsch, and Arvind Krishnamurthy. 2004. Load Balancing and Locality in Range-queriable Data Structures. In Proceedings of the Twentythird Annual ACM Symposium on Principles of Distributed Computing (PODC '04). ACM, New York, NY, USA, 115--124.
6. Baruch Awerbuch and Christian Scheideler. 2004. The Hyperring: A Lowcongestion Deterministic Data Structure for Distributed Environments. In Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '04). Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 318--327. http://dl.acm.org/citation.cfm?id=982792.982836
7. J. Baker, A. Cunei, T. Kalibera, F. Pizlo, and J. Vitek. 2009. Accurate garbage collection in uncooperative environments revisited. Concurrency and Computation: Practice and Experience 21, 12 (2009), 1572--1606.
8. Walter L Bateman. 1990. Open to Question. The Art of Teaching and Learning by Inquiry. ERIC.
9. Jon Beck, Brent Buckner, and Olga Nikolova. 2007. Using Interdisciplinary Bioinformatics Undergraduate Research to Recruit and Retain Computer Science Students. SIGCSE Bull. 39, 1 (March 2007), 358--361.
10. Hans-Juergen Boehm and Mark Weiser. 1988. Garbage Collection in an Uncooperative Environment. Softw. Pract. Exper. 18, 9 (Sept. 1988), 807--820.
11. Sanneke Bolhuis. 2003. Towards process-oriented teaching for self-directed lifelong learning: a multidimensional perspective. Learning and instruction 13, 3 (2003), 327--347.
12. John B. Bowles, Caroline M. Eastman, and Csilla Farkas. 2006. Engaging Undergraduates in Computer Security Research. In Proceedings of the 3rd Annual Conference on Information Security Curriculum Development (InfoSecCD '06). ACM, New York, NY, USA, 184--190.
13. J Bransford, A Brown, and R Cocking. 2000. How people learn: Brain, mind, experience and school. Washington, DC: Commission on Behavioral and Social Sciences and Education, National Research Council. (2000).
14. M. A. Breuer, M. Sarrafzadeh, and F. Somenzi. 2000. Fundamental CAD algorithms. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 19, 12 (Dec 2000), 1449--1475.
15. Jerome S Bruner. 1961. The act of discovery. Harvard educational review (1961).
16. Philip C Candy. 1991. Self-Direction for Lifelong Learning. A Comprehensive Guide to Theory and Practice. ERIC.
17. Jui-Ming Chang and M. Pedram. 2000. Codex-dp: co-design of communicating systems using dynamic programming. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 19, 7 (Jul 2000), 732--744.
18. Shang-Tse Chuang, A. Goel, N. McKeown, and B. Prabhakar. 1999. Matching output queueing with a combined input/output-queued switch. IEEE Journal on Selected Areas in Communications 17, 6 (Jun 1999), 1030--1039.
19. Ian Clarke, Oskar Sandberg, Brandon Wiley, and Theodore W. Hong. 2001. Freenet: A Distributed Anonymous Information Storage and Retrieval System. Springer Berlin Heidelberg, Berlin, Heidelberg, 46--66.
20. Pradipta De. 2004. Data Path Processing in Fast Programmable Routers. CoRR cs.NI/0411070 (2004). http://arxiv.org/abs/cs.NI/0411070
21. Mikael Degermark, Andrej Brodnik, Svante Carlsson, and Stephen Pink. 1997. Small Forwarding Tables for Fast Routing Lookups. SIGCOMM Comput. Commun. Rev. 27, 4 (Oct. 1997), 3--14.
22. John Dewey. 1997. How we think. Courier Corporation.
23. Lieven Eeckhout. 2010. Computer architecture performance evaluation methods. Synthesis Lectures on Computer Architecture 5, 1 (2010), 1--145.
24. Noel Entwistle. 2008. Taking stock: teaching and learning research in higher education. In Review prepared for an international symposium on" Teaching and Learning Research in Higher Education", Guelph, Ontario.
25. Ali Erkan and John Barr. 2016. Algorithms + Organization = Systems. In Proceedings of the 2016 ACM Conference on Innovation and Technology in Computer Science Education (ITiCSE '16). ACM, New York, NY, USA, 65--70.
26. Ali Erkan, Sam Newmark, and Nicolas Ommen. 2009. Exposure to Research Through Replication of Research: A Case in Complex Networks. SIGCSE Bull. 41, 3 (July 2009), 114--118.
27. Philip W.L. Fong. 2009. Reading a Computer Science Research Paper. SIGCSE Bull. 41, 2 (June 2009), 138--140.
28. CT Fosnot. 1996. Constructivism: Theory, Perspectives and Practice. Teachers College Press.
29. Eran Gal and Sivan Toledo. 2005. Algorithms and Data Structures for Flash Memories. ACM Comput. Surv. 37, 2 (June 2005), 138--163.
30. Ulrich Germann, Eric Joanis, and Samuel Larkin. 2009. Tightly Packed Tries: How to Fit Large Models into Memory, and Make Them Load Fast, Too. In Proceedings of the Workshop on Software Engineering, Testing, and Quality Assurance for Natural Language Processing (SETQA-NLP '09). Association for Computational Linguistics, Stroudsburg, PA, USA, 31--39. http://dl.acm.org/citation.cfm? id=1621947.1621952
31. Alejandro F. GonzÃąlez. 1995. Optimization Techniques in VLSI Physical CAD. . EECS Dept., Univ. of Michigan, Ann Arbor MI 48109--2122, Final Report, EECS 527.
32. Michael T. Goodrich, Michael J. Nelson, and Jonathan Z. Sun. 2006. The Rainbow Skip Graph: A Fault-tolerant Constant-degree Distributed Data Structure. In Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm (SODA '06). Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 384--393. http://dl.acm.org/citation.cfm?id=1109557.1109601
33. G. Graefe and P. A. Larson. 2001. B-tree indexes and CPU caches. In Proceedings 17th International Conference on Data Engineering. 349--358.
34. Tony Greening and Judy Kay. 2002. Undergraduate Research Experience in Computer Science Education. SIGCSE Bull. 34, 3 (June 2002), 151--155.
35. Ferenc Havasi. 2011. An Improved B+ Tree for Flash File Systems. In 37th Conference on Current Trends in Theory and Practice of Computer Science. 297-- 307.
36. J. P. Hayes. 1976. A Graph Model for Fault-Tolerant Computing Systems. IEEE Trans. Comput. C-25, 9 (Sept 1976), 875--884.
37. Steffen Heinz, Justin Zobel, and Hugh E. Williams. 2002. Burst Tries: A Fast, Efficient Data Structure for String Keys. ACM Trans. Inf. Syst. 20, 2 (April 2002), 192--223.
38. Suranga Hettiarachchi, Eli Cohen, Timothy Willey, and Nathan Schmidt. 2008. Simulating Mobile Robots for Undergraduate Research. J. Comput. Sci. Coll. 23, 6 (June 2008), 181--186. http://dl.acm.org/citation.cfm?id=1352383.1352416
39. Richard C. Holt. 1972. Some Deadlock Properties of Computer Systems. ACM Comput. Surv. 4, 3 (Sept. 1972), 179--196.
40. Philip W Howard and Jonathan Walpole. 2014. Relativistic red-black trees. Concurrency and Computation: Practice and Experience 26, 16 (2014), 2684--2712.
41. Association for Computing Machinery (ACM) Joint Task Force on Computing Curricula and IEEE Computer Society. 2013. Computer Science Curricula 2013: Curriculum Guidelines for Undergraduate Degree Programs in Computer Science. ACM, New York, NY, USA. 999133.
42. M Tim Jones. 2009. Inside the linux 2.6 completely fair scheduler. IBM Developer Works Technical Report 2009 (2009).
43. Andrew B Kahng, Jens Lienig, Igor L Markov, and Jin Hu. 2011. VLSI Physical Design: From Graph Partitioning to Timing Closure. Springer, 33--40.
44. Andrew B Kahng, Jens Lienig, Igor L Markov, and Jin Hu. 2011. VLSI Physical Design: From Graph Partitioning to Timing Closure. Springer, Chapter Global and Detailed Placement, 95--112.
45. Andrew B Kahng, Jens Lienig, Igor L Markov, and Jin Hu. 2011. VLSI Physical Design: From Graph Partitioning to Timing Closure. Springer, Chapter Global Routing, 131--145.
46. Andrew B Kahng, Jens Lienig, Igor L Markov, and Jin Hu. 2011. VLSI Physical Design: From Graph Partitioning to Timing Closure. Springer, Chapter Detailed Routing, 169--177.
47. David Karger, Eric Lehman, Tom Leighton, Rina Panigrahy, Matthew Levine, and Daniel Lewin. 1997. Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web. In Proceedings of the Twenty-ninth Annual ACM Symposium on Theory of Computing (STOC '97). ACM, New York, NY, USA, 654--663.
48. Charlie Kaufman, Radia Perlman, and Mike Speciner. 2002. Network security: private communication in a public world. Prentice Hall Press.
49. Martin Kaufmann, Amin Amiri Manjili, Panagiotis Vagenas, Peter Michael Fischer, Donald Kossmann, Franz Färber, and Norman May. 2013. Timeline index: A unified data structure for processing queries on temporal data in SAP HANA. In Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data. ACM, 1173--1184.
50. S Keshav. 2007. How to read a paper. ACM SIGCOMM Computer Communication Review 37, 3 (2007), 83--84.
51. P. V. Knudsen and J. Madsen. 1996. PACE: a dynamic programming algorithm for hardware/software partitioning. In Hardware/Software Co-Design, 1996. (Codes/CASHE '96), Proceedings., Fourth International Workshop on. 85--92.
52. Michael E. Kounavis, Andrew T. Campbell, Stephen T. Chou, and John Vicente. 2005. Programming the data path in network processor-based routers. Software: Practice and Experience 35, 11 (2005), 1041--1078.
53. J Kurose and K Ross. 2013. Computer networking: a top-down approach. Always Learning. Pearson, London.
54. Roy Levin and David D. Redell. 1983. An evaluation of the ninth SOSP submissions or: How (and how not) to write a good systems paper. Operating Systems Review 17, 3 (1983), 35--40.
55. Tong Li, Dan Baumberger, and Scott Hahn. 2009. Efficient and Scalable Multiprocessor Fair Scheduling Using Distributed Weighted Round-robin. SIGPLAN Not. 44, 4 (Feb. 2009), 65--74.
56. Rafael D. Lins. 1992. Cyclic Reference Counting with Lazy Mark-scan. Inf. Process. Lett. 44, 4 (Dec. 1992), 215--220.
57. William F Long. 2003. Dissonance detected by cluster analysis of responses to the approaches and study skills inventory for students. Studies in Higher Education 28, 1 (2003), 21--35.
58. Enyue Lu, Mei Yang, Yi Zhang, and S. Q. Zheng. 2003. Design and implementation of an acyclic stable matching scheduler. In Global Telecommunications Conference, 2003. GLOBECOM '03. IEEE, Vol. 7. TBD, 3938--3942 vol.7.
59. Haibin Lu and S. Sahni. 2004. Enhanced interval trees for dynamic IP routertables. IEEE Trans. Comput. 53, 12 (Dec 2004), 1615--1628.
60. Ann Macaskill and Elissa Taylor. 2010. The development of a brief measure of learner autonomy in university students. Studies in Higher Education 35, 3 (2010), 351--359.
61. Claudio Maia, LuÄśs Nogueir, and LuÄśs Miguel Pinho. 2010. Evaluating Android OS for Embedded Real-Time Systems. In 6th International Workshop on Operating Systems Platforms for Embedded Real-Time Applications (OSPERT 2010). 63--70.
62. Terrence Mak, Peter YK Cheung, Kai-Pui Lam, and Wayne Luk. 2011. Adaptive routing in network-on-chips using a dynamic-programming network. IEEE transactions on industrial electronics 58, 8 (2011), 3701--3716.
63. A. D. Martínez, R. Wachenchauzer, and R. D. Lins. 1990. Cyclic Reference Counting with Local Mark-scan. Inf. Process. Lett. 34, 1 (Feb. 1990), 31--35.
64. Ference Marton, Dai Hounsell, and Noel James Entwistle. 1997. The experience of learning: Implications for teaching and studying in higher education. Scottish Academic Press.
65. Ference Marton and R Säaljö. 1976. On qualitative differences in learning?ii Outcome as a function of the learner's conception of the task. british Journal of educational Psychology 46, 2 (1976), 115--127.
66. J. McQuillan, I. Richer, and E. Rosen. 1980. The New Routing Algorithm for the ARPANET. IEEE Transactions on Communications 28, 5 (May 1980), 711--719.
67. M. Muthuprasanna and G. Manimaran. 2008. Distributed Divide-and-Conquer Techniques for Effective DDoS Attack Defenses. In 2008 The 28th International Conference on Distributed Computing Systems. 93--102.
68. Joan Peckham, Peter Stephenson, Jean-Yves Hervé, Ron Hutt, and Miguel Encarnação. 2007. Increasing Student Retention in Computer Science Through Research Programs for Undergraduates. SIGCSE Bull. 39, 1 (March 2007), 124-- 128.
69. Ken Peffers, Tuure Tuunanen, Marcus A. Rothenberger, and Samir Chatterjee. 2007. A Design Science Research Methodology for Information Systems Research. Journal of Management Information Systems 24, 3 (2007), 45--77. arXiv:http://www.tandfonline.com/doi/pdf/10.2753/MIS0742--1222240302
70. Ben Pfaff. 2004. Performance Analysis of BSTs in System Software. SIGMETRICS Perform. Eval. Rev. 32, 1 (June 2004), 410--411.
71. Ben Pfaff, Justin Pettit, Teemu Koponen, Ethan J Jackson, Andy Zhou, Jarno Rajahalme, Jesse Gross, Alex Wang, Joe Stringer, Pravin Shelar, et al. 2015. The Design and Implementation of Open vSwitch.. In NSDI. 117--130.
72. Jean Piaget and Barbel Inhelder. 2008. The psychology of the child. Basic books.
73. Paul R Pintrich, David AF Smith, Teresa Garcia, and Wilbert J McKeachie. 1993. Reliability and predictive validity of the Motivated Strategies for Learning Questionnaire (MSLQ). Educational and psychological measurement 53, 3 (1993), 801--813.
74. Michael J Prince and Richard M Felder. 2006. Inductive teaching and learning methods: Definitions, comparisons, and research bases. Journal of engineering education 95, 2 (2006), 123--138.
75. Aleksandar Prokopec, Nathan Grasso Bronson, Phil Bagwell, and Martin Odersky. 2012. Concurrent tries with efficient non-blocking snapshots. In Acm Sigplan Notices, Vol. 47. ACM, 151--160.
76. Imad Rahal. 2008. Undergraduate Research Experiences in Data Mining. SIGCSE Bull. 40, 1 (March 2008), 461--465.
77. Paul Ramsden et al. 1997. The context of learning in academic departments. The experience of learning 2 (1997), 198--216.
78. Jun Rao and Kenneth A. Ross. 2000. Making B+- Trees Cache Conscious in Main Memory. SIGMOD Rec. 29, 2 (May 2000), 475--486.
79. Sonny Rao, Dominique Heger, and Steven Pratt. 2005. Examining Linux 2.6 Page-Cache Performance. In Proceedings of the Linux Symposium. Red Hat, Inc, 79--90. https://ols.fedoraproject.org/OLS/Reprints-2005/LinuxSymposium2005_ V2.pdf#page=87
80. Sylvia Ratnasamy, Paul Francis, Mark Handley, Richard Karp, and Scott Shenker. 2001. A Scalable Content- able Network. SIGCOMM Comput. Commun. Rev. 31, 4 (Aug. 2001), 161--172.
81. John TE Richardson. 2000. Researching student learning: Approaches to studying in campus-based and distance education. Open University Press.
82. M. A. Ruiz-Sanchez, E. W. Biersack, and W. Dabbous. 2001. Survey and taxonomy of IP lookup algorithms. IEEE Network 15, 2 (Mar 2001), 8--23.
83. Christian S. Sallaberger and Gabriele M.T. D'Eleuterio. 1995. Optimal robotic path planning using dynamic programming and randomization. Acta Astronautica 35, 2 (1995), 143 -- 156. Astrodynamics.
84. Devavrat Shah, P. Giaccone, and Balaji Prabhakar. 2001. An efficient randomized algorithm for input-queued switch scheduling. In HOT 9 Interconnects. Symposium on High Performance Interconnects. 3--8.
85. M. Shaw. 2003. Writing good software engineering research papers. In 25th International Conference on Software Engineering, 2003. Proceedings. 726--736.
86. Abraham Silberschatz, Peter Baer Galvin, and Greg Gagne. 2014. Operating system concepts essentials. John Wiley & Sons, Inc.
87. Stefan Sprenger, Steen Zeuch, and Ulf Leser. 2016. Cache-Sensitive Skip List: E cient Range Queries on modern CPUs. In Data Management on New Hardware, S. Blanas, R. Bordawekar, T. Lahiri, J. Levandoski, and A. Pavlo (Eds.). Springer International Publishing AG.
88. John R Staver and Mary Bay. 1987. Analysis of the project synthesis goal cluster orientation and inquiry emphasis of elementary science textbooks. Journal of Research in Science Teaching 24, 7 (1987), 629--643.
89. Ion Stoica, Robert Morris, David Karger, M. Frans Kaashoek, and Hari Balakrishnan. 2001. Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications. SIGCOMM Comput. Commun. Rev. 31, 4 (Aug. 2001), 149--160.
90. Rahman Tashakkori. 2005. Encouraging Undergraduate Research: A Digital Image Processing Approach. J. Comput. Sci. Coll. 20, 3 (Feb. 2005), 173--180. http://dl.acm.org/citation.cfm?id=1040196.1040218
91. Kate L Turabian. 2013. A manual for writers of research papers, theses, and dissertations: Chicago style for students and researchers. University of Chicago Press.
92. Lev Semenovich Vygotsky. 1980. Mind in society: The development of higher psychological processes. Harvard university press.
93. Kevin Warburton. 2003. Deep learning and education for sustainability. International Journal of Sustainability in Higher Education 4, 1 (2003), 44--56.
94. Maryellen Weimer. 2002. Learner-centered teaching: Five key changes to practice. John Wiley & Sons.
95. Claire E Weinstein, Ann C Schulte, and Anita Woolfolk Hoy. 1987. LASSI: Learning and study strategies inventory. H & H Publishing Company.
96. Petrie Wong, Ziqiang Feng, Wenjian Xu, Eric Lo, and Ben Kao. 2015. TLB Misses: The Missing Issue of Adaptive Radix Tree?. In Proceedings of the 11th International Workshop on Data Management on New Hardware (DaMoN'15). ACM, New York, NY, USA, Article 6, 7 pages.
97. H. Xu and B. Li. 2011. Egalitarian stable matching for VM migration in cloud computing. In 2011 IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS). 631--636.
98. D. Zappala. 2004. Alternate path routing for multicast. IEEE/ACM Transactions on Networking 12, 1 (Feb 2004), 30--43.
99. Barry J Zimmerman. 2002. Becoming a self-regulated learner: An overview. Theory into practice 41, 2 (2002), 64--70.
100. Barry J Zimmerman and Dale H Schunk. 2001. Self-regulated learning and academic achievement: Theoretical perspectives. Routledge.
101. Aviv Zohar. 2015. Bitcoin: Under the Hood. Commun. ACM 58, 9 (Aug. 2015), 104--113.
102. Benjamin Zorn. 1993. The Measured Cost of Conservative Garbage Collection. Softw. Pract. Exper. 23, 7 (July 1993), 733--756.

Index Terms

• Applied computing

  • Education

• Hardware

  • Very large scale integration design

    • VLSI design manufacturing considerations

• Networks

• Software and its engineering

  • Software organization and properties

    • Contextual software domains

      • Operating systems

• Theory of computation

  • Design and analysis of algorithms

    • Data structures design and analysis

    • Graph algorithms analysis