text:
Diablo II

Diablo II is an action role-playing hack-and-slash video game developed by Blizzard North and published by Blizzard Entertainment in 2000 for Microsoft Windows, Classic Mac OS, and OS X. The game, with its dark fantasy and horror themes, was conceptualized and designed by David Brevik and Erich Schaefer, who, with Max Schaefer, acted as project leads on the game. The producers were Matthew Householder and Bill Roper. The game was developed over a three-year period, with a crunch time of a year and a half.

Set shortly after the events of Diablo, the player controls a new hero, attempting to stop the destruction unleashed by Diablo's return. The game's four acts feature a variety of locations and settings to explore and battle in, as well as an increased cast of characters to play as and interact with.

Building on the success of its predecessor, Diablo (1997), and improving the gameplay, both in terms of updated character progression and a better-developed story, Diablo II was one of the most popular games of 2000 and has been cited as one of the greatest games of all time. Major factors that contributed to the game's success include its continuation of popular fantasy themes from the previous game and its access to Blizzard's free online play service, Battle.net. An expansion to the game, Diablo II: Lord of Destruction, was released in 2001.

Diablo III, the sequel to Diablo II, was released on May 15, 2012. Diablo II: Resurrected, a remastered version of Diablo II which also includes the Lord of Destruction expansion, was released on September 23, 2021.

Gameplay
Diablo II's storyline progresses through four chapters or "acts". Each act follows a predetermined path, but the wilderness and dungeons between key areas are randomly generated. The player progresses through the story by completing a series of quests within each act, while there are also optional side dungeons for extra monsters and experience. In contrast to the first Diablo, whose levels consisted of descending deeper and deeper into a Gothic-themed dungeon and Hell, Diablo II's environments are much more varied. Act I is similar to the original Diablo; the Rogue Encampment is a simple palisade fort, with plains and boreal forests making up the wilderness area, and the Monastery resembles the typical medieval fortress. Act II mimics Ancient Egypt's desert and tombs; Lut Gholein resembles a Middle Eastern city and palace during the Crusades. Act III is supposedly based on the Central American jungles; Kurast is inspired by the lost Mayan civilization. Act IV takes place in Hell and is the shortest, with just three quests compared to the other Acts that have six.

The Lord of Destruction expansion adds the fifth chapter Act V which continues the story where Act IV left off. Act V's style is mainly mountainous as the player ascends Mount Arreat, with alpine plateaus and icy tunnels and caverns. Occasional portals can take the player to dungeons in Hell (seen in Act IV) for extra monsters and experience. After reaching the summit of Arreat, the player gains access to the Worldstone Keep.

In addition to the acts, there are three sequential difficulty levels: Normal, Nightmare, and Hell; completing the game (four Acts in the original or five Acts in the expansion) on a difficulty setting will open up the next level. On higher difficulties, monsters are more varied, stronger, and may be resistant or immune to an element or physical damage; experience is penalized on dying, and the player's resistances are handicapped. However, better items are rewarded to players as they go through higher difficulties. A character retains all abilities and items between difficulties and may return to a lower difficulty at any time, albeit it is not possible to replay the quests that are already completed.

Players can create a hardcore character. In normal mode, the player can resurrect their character if killed and resume playing, while a hardcore character has only one life. If killed, the character is permanently dead and unplayable. In addition, all items and equipment on that character will be lost unless another friendly character has the "loot" icon checked. Standard and hardcore characters play on separate online channels; as such a hardcore player can never appear in the same game session as a standard player.

Item system
Diablo II uses a system of randomly generated equipment similar to the original Diablo, but more complicated. Weapons and armor are divided into several quality levels: normal, magical, set, rare, and unique. Normal quality items are base items with a fixed set of basic properties, such as attribute requirements, maximum durability, armor rating (on armor), block chance (on shields), damage, and attack speed (on weapons). Magical quality items have blue names and one or two randomly selected bonuses, such as bonuses attributes, skills, or damage, indicated by a prefix or suffix. Rare quality items have randomly generated yellow names and 2 to 6 random properties. Unique items have fixed names in gold text, and instead of randomized properties, they have a set of 3 to 8 preselected properties. Green-named set items have fixed names and preselected properties like unique items, and belong to specifically named sets of 2 to 6 items. Additional properties known as set bonuses are activated by equipping multiple or all items from the same set. These are themed on individuals, like Civerb's cudgel, shield, and amulet, each of which provides individual bonuses which are enhanced if two or more of the items are used to equip a character. It is unusual to encounter more than one item from a set in a single playthrough of the game, so collectors need to play the game many times to accumulate all items from a set or purchase them online from other players who possess them but do not need them. Additionally, items can possess sockets, which can be used to upgrade items by adding gems for various bonuses.

Diablo II includes an item crafting system. An item called the Horadric Cube is used to combine two or more items to create a new item. For example, three identical lower-quality gems can be combined to create a single higher-quality gem, and three small rejuvenation potions can be combined to create a single, more powerful rejuvenation potion.

Character classes

Diablo II allows the player to choose between five different character classes: Amazon, Necromancer, Barbarian, Sorceress, and Paladin. Each character has different strengths, weaknesses, and sets of skills to choose from, as well as varying beginning attributes. The maximum level that any character can obtain is level 99.

 * The Amazon hails from the islands of the Twin Seas, near the border of the Great Ocean. The Amazon is akin to the Rogue of Diablo: both primarily use bows and both make equal use of strength and magic but the Amazon can also use javelins and spears. As such, her clan is a rival to the Sisters of the Sightless Eye (also known as Rogues). Many of her defensive skills are passive in nature, especially Dodge, Avoid, and Evade. The Amazon is voiced by Jessica Straus.
 * The Necromancer is a versatile death-themed spell caster. Necromancers are the priests of the Cult of Rathma from the Eastern jungles. His Summoning skills allow him to raise skeletons, create golems and resurrect dead monsters to fight alongside him. The Necromancer possesses powerful poison spells, which rapidly drain life from afflicted monsters. He also has "Bone" skills, which directly damage enemies while bypassing most resistances. His Curses also afflict the enemy with debilitating status ailments, sowing confusion and chaos in their ranks. The Necromancer is voiced by Michael McConnohie.
 * The Barbarian is a powerful melee fighter who resides on the steppes of Mount Arreat. The Barbarian is akin to the Warrior of Diablo: both are experts with all weapons for frontline combat and both are able to absorb major punishment. As such, the Barbarian is the only class capable of dual wielding weapons. His Combat Masteries allow him to specialize in different types of weapons and also passively increase his resistance, speed, and defense. His Warcries dramatically increase the combat effectiveness of him and his party, as well as afflicting status ailments on enemies. He has a variety of Combat Skills at his command, most of which focus on delivering great force upon a single foe, while some also allow him to leap over chasms and rivers. The Barbarian is voiced by David Thomas.
 * The Sorceress hails from a rebellious coven of female witches who have wrested the secrets of magic from the male-dominated mage clans of the East. She can cast lightning, fire and ice spells. Most of the lightning and fire spells are carried over from the original Diablo, the ice spells can freeze enemies solid and bypass resistances while doing less damage than lightning or fire. Nearly all of these skills are offensive in nature by besieging the enemy with elemental calamity. The Sorceress's Teleport spell allows her to instantly travel to a new destination, allowing her to quickly traverse dungeons as well as making her very difficult to hit. The strength of the Sorceress is her damaging spells and casting speed; her weakness is her relatively low hit points and defense. The Sorceress is voiced by Liana Young.
 * The Paladin is a crusader from the Church of Zakarum, fighting for the glory of the Light. He was part of the forces that defeated King Leoric's army in the first Diablo, although his Order is eventually corrupted by Mephisto, the Lord of Hatred. To reflect his holy nature, the Paladin's combat skills range from fanatical attacks to heavenly thunderbolts. His loadout is split into Combat Skills, Defensive Auras and Offensive Auras. His auras have a range of abilities such as increasing damage, resisting magic attacks or boosting defense. Most auras either affect all party members and allies or all enemies within the area of effect. The Paladin also has specialized skills for eliminating the undead and is highly proficient in the use of a shield, being the only class that can use it as a weapon. The Paladin is voiced by Larry B. Scott.

Two additional character classes, the Druid and Assassin, were added in the expansion Diablo II: Lord of Destruction.

 * The Druid is a shapeshifter with the ability to transform into a werewolf or werebear form. He can summon wild animals such as ravens or wolves as allies and attack with nature-based vines or elemental magic like wind or fire. The Druid offers a wide versatility of skills and can be built in several different playstyles. The Druid is voiced by Michael Bell.
 * The Assassin is a martial arts-based class from the Viz-Jaq'taar clan who fights with claw blades and supplements her attacks with the use of shadow magic skills and fire or lightning elemental traps, which remain stationary and affect groups of enemies. The Assassin is voiced by Carrie Gordon.

The player can enlist the help of one hireling (computer-controlled mercenaries) from a mercenary captain in the town; Rogue Scouts (archers with Amazon abilities), Desert Mercenaries or Town Guards (melee fighters with Paladin auras), Iron Wolves (elemental spellcasters with occasional melee capability), and Barbarians (melee fighters with many hitpoints), from Acts I, II, III, and V, respectively. In the original release of the game, hirelings would not follow the player through different Acts, nor be revived if killed. The expansion allows players to retain their mercenary throughout the entire game as well as equipping them with armor and weapons, plus hirelings gain experience and attributes like the player although their level cannot surpass that of their master character. Typically, players choose a hireling that provides something missing from their character class; for instance, the melee-focused Paladin may choose an Iron Wolf for ranged magical support.

In Heroes of the Storm (2015), playable characters Cassia and Xul represent the Amazon and the Necromancer classes, respectively.

Multiplayer
Diablo II can be played multiplayer on a local area network (LAN) or the Blizzard's Battle.net online service. Unlike the original Diablo, Diablo II was made specifically with online gaming in mind. Several spells (such as auras or war cries) multiply their effectiveness if they are cast within a party, and although dungeons still exist, they were largely replaced by open spaces.

Battle.net is divided into "Open" and "Closed" realms. Single-player characters may be played on open realms; only Battle.net characters that are stored on Blizzard's servers may be played on closed realms as a measure against cheating, where they must be played at least once every 90 days to avoid expiration. Open games are subject to many abuses as the characters are stored on the players' own hard drives. Many cheats that were used on closed realms do not exist or work any longer. Hacks, bots, and programs which allow the player to run multiple instances of the game at the same time are not allowed by Blizzard. They are rarely used anymore. Blizzard cracked down on spambots which advertise sites selling Diablo II's virtual items for real-world currency.

As the game can be played cooperatively (Players vs. Environment, PvE), groups of players with specific sets of complementary skills can finish some of the game's climactic battles in a matter of seconds, providing strong incentives for party-oriented character builds. Up to eight players can be in one game; they can either unite as a single party, play as individuals, or form multiple opposing parties. Experience gained, monsters' hit points and damage, and the number of items dropped are all increased as more players join a game, though not in a strictly proportional manner. Players are allowed to duel each other with all damage being reduced in player vs player (PvP). The bounty for a successful kill in PvP is a portion of the gold and the "ear" of the defeated player (with the previous owner's name and level at the time of the kill).

The Ladder System is reset at various intervals by Blizzard to allow for all players to start fresh with new characters on an equal footing. Ladder seasons have lasted from as short as six months to over a year. When a ladder season ends, all ladder characters are transferred to the non-ladder population. Certain rare items are available only within ladder games, although they can be traded for and exchanged on non-ladder after the season has ended.

The game has been patched extensively; the precise number of patches is impossible to determine as Battle.net has the capability of making minor server-side patches to address urgent bugs. , the game is in version 1.14d. Through the patch history, several exploits and bugs such as item duplication have been addressed, as well as major revamps to the game's balance (such as the ability to redo skills and attributes). Not all patches have affected Diablo II directly, as several were designed to address aspects of the expansion to the game and had minimal effects on Diablo II.

Plot
Diablo II takes place after the end of the previous game, Diablo, in the world of Sanctuary. In Diablo, an unnamed warrior defeated Diablo and attempted to contain the Lord of Terror's essence within his own body. Since then, the hero has become corrupted by the demon's spirit, causing demons to enter the world around him and wreak havoc.

A band of adventurers who pass through the Rogue Encampment hear these stories of destruction and attempt to find out the cause of the evil, starting with this corrupted "Dark Wanderer." As the story develops, the truth behind this corruption is revealed: the soulstones were originally intended to imprison the Prime Evils after they were banished to the mortal realm by the Lesser Evils. With the corruption of Diablo's soulstone, the demon is able to control the Dark Wanderer and is attempting to free his two brothers, Mephisto and Baal. Baal, united with the mage Tal-Rasha, is imprisoned in a tomb near Lut Gholein. Mephisto is imprisoned in the eastern temple city of Kurast.

As the story progresses, cut scenes show the Dark Wanderer's journey as a drifter named Marius follows him. Marius, now in an asylum, narrates the events to a hooded visitor, whom he initially believes to be the Archangel Tyrael. The player realizes that the Dark Wanderer's mission is to reunite with the other prime evils, Baal and Mephisto. The story is divided up into four acts:

 * Act I – The adventurers rescue Deckard Cain, who is imprisoned in Tristram, and then begin following the Dark Wanderer. The Dark Wanderer has one of the lesser evils, Andariel, corrupt the Sisters of the Sightless Eye (Rogues) and take over their Monastery. The adventurers overcome Andariel and then follow the Wanderer east.
 * Act II – While the adventurers search the eastern desert for Tal-Rasha's tomb, the Dark Wanderer gets there first. Marius is tricked into removing Baal's soulstone from Tal-Rasha and Tyrael charges Marius with taking the soulstone to Hell to destroy it.
 * Act III – The Dark Wanderer and Baal look for Mephisto in the Temple of Kurast. Still imprisoned in the dungeon below the temple, Mephisto was able to corrupt the High Council of Zakarum and take over the region. While the adventurers fight their way to the temple, Mephisto is rejoined by his brothers; the three open a portal to Hell, the Dark Wanderer sheds his human form, becomes the demon Diablo, and goes through the portal. The adventurers arrive later, defeat Mephisto, who was left guarding the entrance, and take his soulstone.
 * Act IV – The adventurers slay Diablo in Hell and destroy the soulstones of Mephisto and Diablo on the Hellforge, preventing their return.

In the epilogue, Marius indicates he was too weak to enter Hell, and that he fears the stone's effects on him. He gives the soulstone to his visitor. The visitor reveals himself to actually be Baal, the last surviving Prime Evil now in possession of his own soulstone. He then kills Marius and sets the asylum on fire.

The story continues with Act V, in the expansion Diablo II: Lord of Destruction where Baal attempts to corrupt the mythical Worldstone on Mount Arreat. Upon returning to the Pandemonium Fortress after defeating Diablo, Tyrael opens a portal to send the adventurers to Arreat.

Development
Diablo II was announced by Blizzard in 1997, with a planned launch in the first quarter of 1998. According to designer and project lead Erich Schaefer, "Diablo II never had an official, complete design document... for the most part we just started making up new stuff." The game was slated to have two years of development work, but it took Blizzard North over three years to finish. Diablo II, despite having less than one percent of the original code from Diablo and having much of its content and internal coding done from scratch, was seen by the testers as "more of the same." The game was meant to be released simultaneously both in North America and internationally. This allowed the marketing and PR department for Blizzard North to focus their efforts in building up excitement in players worldwide for the first week of sales, contributing to the game's success. The cover art designed by Gerald Brom originally had a hole in the forehead of the character but the hole was hidden after Columbine High School massacre happened. Over 70 people worked on the game.

A second expansion beyond Lord of Destruction had been in the design stages of development at Blizzard, according to David Brevik, but never reached the production stage. In addition to adding new classes, areas, monsters, and items, the expansion would have brought in more elements of a massively multiplayer online (MMO) game featuring elements like guild halls, what Brevik considered an "ARPG+MMO". Brevik said the expansion was shelved when most of the Blizzard North staff left the company around June 2003.

Music
The score was composed by Matt Uelmen and integrates creepy ambience with melodic pieces. The style of the score is ambient industrial and experimental. It was recorded in Redwood City, Oakland, and San Mateo, California, from April 1997 to March 2000.

Some tracks were created by reusing the tracks from the original game, while others by rearranging tracks that were out-takes. Other scores are combinations of parts that were created more than a year after the first game's release. A single track usually integrates recorded samples from sound libraries, live recorded instrument interpretation samples specially meant for the game (guitar, flute, oriental percussion), and electronic instruments also, making the tracks difficult for later live interpretations.

While the player visits the town, the game recreates the peaceful atmosphere from the first Diablo game, so for that the theme from Act I called "Rogue" comes back with the same chords of the original piece, reproducing only a part of the original Diablo town theme. For Act II Mustafa Waiz, a percussionist, and Scott Petersen, the game's sound designer, worked on the drum samples. Waiz played on the dumbek, djembe, and finger cymbals which gave Matt Uelmen a base upon which to build tracks around.

The town theme from Act II, "Toru", makes strong statement of departure from the world of Act I while also maintaining a thematic connection to what had come before. It is the first time in the series to be used some radically different elements than the guitars and choral sounds that dominate both the original Diablo and the opening quarter of Diablo II. The foundation of the "Toru" piece is found in exciting dynamics of a Chinese wind gong. The instrument radically changes color from a steady mysterious drone to a harsh, fearsome noise, which gives exotic feeling and at the same time the pacing of the second town. In all sequences of Act II with deserts and valleys, Arabic percussion sounds dominate.

The composer was impressed by two of the Spectrasonics music libraries, Symphony of Voices and Heart of Asia. He used samples from Heart of Asia in the Harem piece from Act II. The "Crypt" track uses a sample from Symphony of Voices; the choral phrase Miserere. Voice samples from Heart of Asia, Heart of Africa, and Symphony of Voices by Spectrasonics. The "Harem" track samples from Heart of Asia the Sanskrit Female 1 samples.

Release
The game was released in Collector's Edition format, containing bonus collector's material, a copy of the Diablo Dungeons & Dragons pen-and-paper campaign setting, and promotional movies for other Blizzard games. In 2000, the Diablo II: Exclusive Gift Set similarly contained exclusive collector's material and promotional videos, as well as a copy of the official strategy guide. The 2000 released Diablo Gift Pack contained copies of Diablo and Diablo II, but no expansions. The 2001 Diablo: Battle Chest version contained copies of Diablo II, Diablo II: Lord of Destruction, the official strategy guide, and the original Diablo. Recently however, the Battle Chest edition no longer contains the original Diablo.

Support and legacy
Blizzard continues to provide limited support for Diablo II, including occasional patches. Although the original CD retail release worked on Windows 95/98/Me/NT4SP5, the current version downloadable from Battle.net requires at least Windows 2000/XP.

Around 2008, the announcement of Diablo III renewed the interest in its predecessor and brought more attention to the many mods available for the game.

In 2015, an unofficial port for the ARM architecture-based Pandora handheld became available by static recompilation and reverse engineering of the original x86 version.

On March 11, 2016, Blizzard released the 1.14a Patch, which added support for Windows 7 and newer, a macOS installer and support for OS X 10.10 and 10.11. Diablo II is not supported on macOS 10.15, due to Apple completely dropping compatibility with 32-bit binaries in this version.

Diablo II: Resurrected
A remaster of the original and expansion, entitled Diablo II: Resurrected, was released in 2021 for Windows, PlayStation 4, PlayStation 5, Xbox One, Xbox Series X and Series S, and Nintendo Switch. The remaster includes updated graphics and re-rendering of the game's cutscenes, and supports cross-progression between the different platforms. The remastered version supports online features for players within the same console family, but not local co-op. Cross-platform play was not available upon release, although there is a possibility of it being included in a future update. The game also features quality-of-life improvements that Blizzard can implement by taking advantage of modern computers and consoles, including support for controllers on all systems, easier means of item identification, and shared stashes of items between all of a player's characters. But the designers also forego elements such as quest markers that are common in modern games, preserving as much of the original experience as possible, and making the re-master almost completely unchanged from the original Diablo II.

Critical reviews
Diablo II has a positive reception. The PC version of the game achieves an overall score of 88/100 on Metacritic and 89% at GameRankings. GameSpy awarded the game an 86 out of 100, IGN awarded the game an 8.3 out of 10, and GameSpot awarded the game an 8.5 out of 10.

Greg Vederman reviewed the PC version of the game for Next Generation, rating it five stars out of five, and stated that "Diablo II is a must-have PC title. That's all there is to it."

Awards
Diablo II earned GameSpot's 2000 runner-up Reader's Choice Award for role-playing game of the year. Diablo II was awarded with "PC Role-Playing Game of the Year", "PC Game of the Year", and "Game of the Year" from the Academy of Interactive Arts and Sciences during the 4th Annual Interactive Achievement Awards. In August 2016, Diablo II placed 21st on Time's The 50 Best Video Games of All Time list. It was placed at No. 8 on Game Informer's "Top 100 RPGs Of All Time" list.

Sales
On its debut day, Diablo II sold 184,000 units. The game's global sales reached 1 million copies after two weeks, and 2 million after one and a half months. It was awarded a spot in the Guinness Book of World Records 2000 edition for being the fastest selling computer game ever, with more than 1 million units sold in the first two weeks of availability. Its sales during 2000 alone reached 2.75 million globally; 33% of these copies were sold outside the United States, with South Korea making up the largest international market. Warcraft III: Reign of Chaos, World of Warcraft: The Burning Crusade, World of Warcraft: Wrath of the Lich King, World of Warcraft: Cataclysm and Diablo III have since surpassed Diablo II's record to become fastest-selling computer games ever at their times of release, according to Blizzard.

In the United States, PC Data tracked 308,923 sales for Diablo II during the June 25–July 1 period, including sales of its Collector's Edition. This drew revenues of $17.2 million. Domestic sales reached 790,285 units ($41.05 million) by the end of October 2000, according to PC Data. Another $4.47 million were earned in the region by that date via sales of the Collector's Edition. Diablo II finished 2000 with 970,131 sales in the United States, for a gross of $48.2 million.

Diablo II's success continued in 2001: from February to the first week of November, it totaled sales of 306,422 units in the United States. It was ultimately the country's eighth best-selling computer title of 2001, with sales of 517,037 units and revenues of $19.3 million. Its lifetime domestic sales climbed to 1.7 million units, for $67.1 million in revenue, by August 2006. At this time, this led Edge to declare it the United States' second-largest computer game hit released since January 2000. It received a "Gold" sales award from the Entertainment and Leisure Software Publishers Association (ELSPA), indicating sales of at least 200,000 copies in the United Kingdom.

Diablo II became a major hit in the German market and debuted at #1 on Media Control's computer game sales chart for June 2000. Speaking with Havas Interactive's public relations director, PC Player's Udo Hoffman noted that the representative "had to make an effort on the phone to avoid singing and jubilating" over the game's commercial performance. The Verband der Unterhaltungssoftware Deutschland (VUD) presented Diablo II with a "Gold" award after three weeks of availability, indicating sales of at least 100,000 units across Germany, Austria and Switzerland. It maintained first place for July and rose to "Platinum" status (200,000 sales) by the end of the month. The game proceeded to place in Media Control's top 10 through October, peaking at #2 in August, and in the top 30 through December. By the end of 2000, roughly 350,000 units had been sold in the German market. Diablo II continued to chart in January 2001, with a placement of 24th, and its Limited Edition debuted in second place for February. That April, the VUD presented the game with a "Double-Platinum" certification, for 400,000 sales. This made it one of the region's best-selling computer games ever at that time.

As of June 29, 2001, Diablo II has sold 4 million copies worldwide. Copies of Diablo: Battle Chest continue to be sold in retail stores, appearing on the NPD Group's top 10 PC games sales list as recently as 2010. Even more remarkably, the Diablo: Battle Chest was the 19th best-selling PC game of 2008 – a full eight years after the game's initial release – and 11 million users still played Diablo II and StarCraft over Battle.net in 2010.

Printed analyses

 * Discusses the development of Diablo (I) and the origins of the Blizzard Entertainment game development studio.
 * Discusses the development of Diablo II specifically.
 * Examines various game design patterns (especially randomization and level progression) used in Diablo II and compares with other action-RPGs to understand why Diablo II was particularly engaging, relative to its competitors.

title: Diablo II


text:
Design

A design is the concept of or proposal for an object, process, or system. The word, design, refers to something that is or has been intentionally created by a thinking agent, although it is sometimes used to refer to the inherent nature of something – its design. The verb to design expresses the process of developing a design. In some cases, the direct construction of an object without an explicit prior plan may also be considered to be a design (such as in arts and crafts). A design is expected to have a purpose within a certain context, usually having to satisfy certain goals and constraints and to take into account aesthetic, functional, economic, environmental, or socio-political considerations. Traditional examples of designs include architectural and engineering drawings, circuit diagrams, sewing patterns, and less tangible artefacts such as business process models.

Designing
People who produce designs are called designers. The term 'designer' generally refers to someone who works professionally in one of the various design areas. Within the professions, the word 'designer' is generally qualified by the area of practice (for example: a fashion designer, a product designer, a web designer, or an interior designer), but it can also designate others such as architects and engineers (see below: Types of designing). A designer's sequence of activities to produce a design is called a design process with some employing designated processes such as design thinking and possibly design methods. The process of creating a design can be brief (a quick sketch) or lengthy and complicated, involving considerable research, negotiation, reflection, modeling, interactive adjustment, and re-design.

Designing is also a widespread activity outside of the professions of those formally recognized as designers. In his influential book The Sciences of the Artificial the interdisciplinary scientist Herbert A. Simon proposed that "Everyone designs who devises courses of action aimed at changing existing situations into preferred ones". And according to the design researcher Nigel Cross "Everyone can – and does – design," and "Design ability is something that everyone has, to some extent, because it is embedded in our brains as a natural cognitive function".

History of design
The study of design history is complicated by varying interpretations of what constitutes 'designing'. Many design historians, such as John Heskett, start with the Industrial Revolution and the development of mass production. Others subscribe to conceptions of design that include pre-industrial objects and artefacts, beginning their narratives of design in prehistorical times. Originally situated within art history, the historical development of the discipline of design history coalesced in the 1970s, as interested academics worked to recognize design as a separate and legitimate target for historical research. Early influential design historians include German-British art historian Nikolaus Pevsner and Swiss historian and architecture critic Sigfried Giedion.

Design education
Institutions for design education date back to the nineteenth century. The Norwegian National Academy of Craft and Art Industry was founded in 1818, followed by the United Kingdom's Government School of Design (1837), Konstfack in Sweden (1844), and Rhode Island School of Design in the United States (1877). Polish "Towarzystwo Polska Sztuka Stosowana" (1901) and Warsztaty Krakowskie (1913). The German art and design school Bauhaus, founded in 1919, greatly influenced modern design education.

Design education covers the teaching of theory, knowledge, and values in the design of products, services, and environments, and focuses on the development of both particular and general skills for designing. Its primary orientation is to prepare students for professional design practice, based around project work and studio or atelier teaching methods.

There are also broader forms of higher education in design studies and design thinking. Design also features as a part of general education, for example within Design and Technology. The development of design in general education in the 1970s created a need to identify fundamental aspects of 'designerly' ways of knowing, thinking, and acting, resulting in the establishment of design as a distinct discipline of study.

Design process
Substantial disagreement exists concerning how designers in many fields, whether amateur or professional, alone or in teams, produce designs. Design researchers Dorst and Dijkhuis acknowledged that "there are many ways of describing design processes", and compare and contrast two dominant but different views of the design process: as a rational problem-solving process and as a process of reflection-in-action. They suggested that these two paradigms "represent two fundamentally different ways of looking at the world – positivism and constructionism". The paradigms may reflect differing views of how designing should be done and how it actually is done, and they both have a variety of names. The problem-solving view has been called "the rational model", "technical rationality" and "the reason-centric perspective". The alternative view has been called "reflection-in-action", "co-evolution", and "the action-centric perspective".

Rational model
The rational model was independently developed by Herbert A. Simon, an American scientist, and two German engineering design theorists, Gerhard Pahl and Wolfgang Beitz. It posits that:
 * 1) Designers attempt to optimize a design candidate for known constraints and objectives.
 * 2) The design process is plan-driven.
 * 3) The design process is understood in terms of a discrete sequence of stages.

The rational model is based on a rationalist philosophy and underlies the waterfall model, systems development life cycle, and much of the engineering design literature. According to the rationalist philosophy, design is informed by research and knowledge in a predictable and controlled manner.

Typical stages consistent with the rational model include the following:

 * Pre-production design
 * Design brief – initial statement of intended outcome.
 * Analysis – analysis of design goals.
 * Research – investigating similar designs in the field or related topics.
 * Specification – specifying requirements of a design for a product (product design specification) or service.
 * Problem solving – conceptualizing and documenting designs.
 * Presentation – presenting designs.
 * Design during production.
 * Development – continuation and improvement of a design.
 * Product testing – in situ testing of a design.
 * Post-production design feedback for future designs.
 * Implementation – introducing the design into the environment.
 * Evaluation and conclusion – summary of process and results, including constructive criticism and suggestions for future improvements.
 * Redesign – any or all stages in the design process repeated (with corrections made) at any time before, during, or after production.

Each stage has many associated best practices.

Criticism of the rational model
The rational model has been widely criticized on two primary grounds:

 * 1) Designers do not work this way – extensive empirical evidence has demonstrated that designers do not act as the rational model suggests.
 * 2) Unrealistic assumptions – goals are often unknown when a design project begins, and the requirements and constraints continue to change.

Action-centric model
The action-centric perspective is a label given to a collection of interrelated concepts, which are antithetical to the rational model. It posits that:

 * 1) Designers use creativity and emotion to generate design candidates.
 * 2) The design process is improvised.
 * 3) No universal sequence of stages is apparent – analysis, design, and implementation are contemporary and inextricably linked.

The action-centric perspective is based on an empiricist philosophy and broadly consistent with the agile approach and methodical development. Substantial empirical evidence supports the veracity of this perspective in describing the actions of real designers. Like the rational model, the action-centric model sees design as informed by research and knowledge.

At least two views of design activity are consistent with the action-centric perspective. Both involve these three basic activities:

 * In the reflection-in-action paradigm, designers alternate between "framing", "making moves", and "evaluating moves". "Framing" refers to conceptualizing the problem, i.e., defining goals and objectives. A "move" is a tentative design decision. The evaluation process may lead to further moves in the design.
 * In the sensemaking–coevolution–implementation framework, designers alternate between its three titular activities. Sensemaking includes both framing and evaluating moves. Implementation is the process of constructing the design object. Coevolution is "the process where the design agent simultaneously refines its mental picture of the design object based on its mental picture of the context, and vice versa".

The concept of the design cycle is understood as a circular time structure, which may start with the thinking of an idea, then expressing it by the use of visual or verbal means of communication (design tools), the sharing and perceiving of the expressed idea, and finally starting a new cycle with the critical rethinking of the perceived idea. Anderson points out that this concept emphasizes the importance of the means of expression, which at the same time are means of perception of any design ideas.

Philosophies
Philosophy of design is the study of definitions, assumptions, foundations, and implications of design. There are also many informal 'philosophies' for guiding design such as personal values or preferred approaches.

Approaches to design
Some of these values and approaches include:
 * Critical design uses designed artefacts as an embodied critique or commentary on existing values, morals, and practices in a culture. Critical design can make aspects of the future physically present to provoke a reaction.
 * Ecological design is a design approach that prioritizes the consideration of the environmental impacts of a product or service, over its whole lifecycle. Ecodesign research focuses primarily on barriers to implementation, ecodesign tools and methods, and the intersection of ecodesign with other research disciplines.
 * Participatory design (originally co-operative design, now often co-design) is the practice of collective creativity to design, attempting to actively involve all stakeholders (e.g. employees, partners, customers, citizens, end-users) in the design process to help ensure the result meets their needs and is usable. Recent research suggests that designers create more innovative concepts and ideas when working within a co-design environment with others than they do when creating ideas on their own.
 * Scientific design refers to industrialised design based on scientific knowledge. Science can be used to study the effects and need for a potential or existing product in general and to design products that are based on scientific knowledge. For instance, a scientific design of face masks for COVID-19 mitigation may be based on investigations of filtration performance, mitigation performance, thermal comfort, biodegradability and flow resistance.
 * Service design is a term that is used for designing or organizing the experience around a product and the service associated with a product's use. The purpose of service design methodologies is to establish the most effective practices for designing services, according to both the needs of users and the competencies and capabilities of service providers.
 * Sociotechnical system design, a philosophy and tools for participative designing of work arrangements and supporting processes – for organizational purpose, quality, safety, economics, and customer requirements in core work processes, the quality of peoples experience at work, and the needs of society.
 * Transgenerational design, the practice of making products and environments compatible with those physical and sensory impairments associated with human aging and which limit major activities of daily living.
 * User-centered design, which focuses on the needs, wants, and limitations of the end-user of the designed artefact. One aspect of user-centered design is ergonomics.

Relationship with the arts
The boundaries between art and design are blurry, largely due to a range of applications both for the term 'art' and the term 'design'. Applied arts can include industrial design, graphic design, fashion design, and the decorative arts which traditionally includes craft objects. In graphic arts (2D image making that ranges from photography to illustration), the distinction is often made between fine art and commercial art, based on the context within which the work is produced and how it is traded.

Types of designing
• Applied arts

• Architecture

• Automotive design

• Biological design

• Cartographic or map design

• Configuration design

• Communication design

• Costume design

• Design management

• Engineering design

• Experience design

• Fashion design

• Floral design

• Game design

• Graphic design

• Information architecture

• Information design

• Industrial design

• Instructional design

• Interaction design

• Interior design

• Landscape architecture

• Lighting design

• Modular design

• Motion graphic design

• Organization design

• Process design

• Product design

• Production design

• Property design

• Scenic design

• Service design

• Social design

• Software design

• Sound design

• Spatial design

• Strategic design

• Systems architecture

• Systems design

• Systems modeling

• Type design

• Urban design

• User experience design

• User interface design

• Vexillography

• Web design

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

title: Design


text:
Denormalization

Denormalization is a strategy used on a previously-normalized database to increase performance. In computing, denormalization is the process of trying to improve the read performance of a database, at the expense of losing some write performance, by adding redundant copies of data or by grouping data. It is often motivated by performance or scalability in relational database software needing to carry out very large numbers of read operations. Denormalization differs from the unnormalized form in that denormalization benefits can only be fully realized on a data model that is otherwise normalized.

Implementation
A normalized design will often "store" different but related pieces of information in separate logical tables (called relations). If these relations are stored physically as separate disk files, completing a database query that draws information from several relations (a join operation) can be slow. If many relations are joined, it may be prohibitively slow. There are two strategies for dealing with this by denormalization:
 * "DBMS support": The database management system stores redundant copies in the background, which are kept consistent by the DBMS software
 * "DBA implementation": The database administrator (or designer) design around the problem by denormalizing the logical data design

DBMS support
With this approach, database administrators can keep the logical design normalized, but allow the database management system (DBMS) to store additional redundant information on disk to optimize query response. In this case it is the DBMS software's responsibility to ensure that any redundant copies are kept consistent. This method is often implemented in SQL as indexed views (Microsoft SQL Server) or materialized views (Oracle, PostgreSQL). A view may, among other factors, represent information in a format convenient for querying, and the index ensures that queries against the view are optimized physically.

DBA implementation
With this approach, a database administrator or designer has to denormalize the logical data design. With care this can achieve a similar improvement in query response, but at a cost — it is now the database designer's responsibility to ensure that the denormalized database does not become inconsistent. This is done by creating rules in the database called constraints, that specify how the redundant copies of information must be kept synchronized, which may easily make the de-normalization procedure pointless. It is the increase in logical complexity of the database design and the added complexity of the additional constraints that make this approach hazardous. Moreover, constraints introduce a trade-off, speeding up reads ( in SQL) while slowing down writes (,  , and  ). This means a denormalized database under heavy write load may offer worse performance than its functionally equivalent normalized counterpart.

Denormalization versus not normalized data
A denormalized data model is not the same as a data model that has not been normalized, and denormalization should only take place after a satisfactory level of normalization has taken place and that any required constraints and/or rules have been created to deal with the inherent anomalies in the design. For example, all the relations are in third normal form and any relations with join dependencies and multi-valued dependencies are handled appropriately.

Examples of denormalization techniques include:
 * "Storing" the count of the "many" elements in a one-to-many relationship as an attribute of the "one" relation
 * Adding attributes to a relation from another relation with which it will be joined
 * Star schemas, which are also known as fact-dimension models and have been extended to snowflake schemas
 * Prebuilt summarization or OLAP cubes

With the continued dramatic increase in all three of storage, processing power and bandwidth, on all levels, denormalization in databases has moved from being an unusual or extension technique, to the commonplace, or even the norm. For example, one specific downside of denormalization was, simply, that it "uses more storage" (that is to say, literally more columns in a database). With the exception of truly enormous systems, use of storage has in the 2020s become relatively seen as a small problem.

title: Denormalization


text:
Differential topology

In mathematics, differential topology is the field dealing with the topological properties and smooth properties of smooth manifolds. In this sense differential topology is distinct from the closely related field of differential geometry, which concerns the geometric properties of smooth manifolds, including notions of size, distance, and rigid shape. By comparison differential topology is concerned with coarser properties, such as the number of holes in a manifold, its homotopy type, or the structure of its diffeomorphism group. Because many of these coarser properties may be captured algebraically, differential topology has strong links to algebraic topology. The central goal of the field of differential topology is the classification of all smooth manifolds up to diffeomorphism. Since dimension is an invariant of smooth manifolds up to diffeomorphism type, this classification is often studied by classifying the (connected) manifolds in each dimension separately:

 * In dimension 1, the only smooth manifolds up to diffeomorphism are the circle, the real number line, and allowing a boundary, the half-closed interval $$[0,1)$$ and fully closed interval $$[0,1]$$.
 * In dimension 2, every closed surface is classified up to diffeomorphism by its genus, the number of holes (or equivalently its Euler characteristic), and whether or not it is orientable. This is the famous classification of closed surfaces. Already in dimension two the classification of non-compact surfaces becomes difficult, due to the existence of exotic spaces such as Jacob's ladder.
 * In dimension 3, William Thurston's geometrization conjecture, proven by Grigori Perelman, gives a partial classification of compact three-manifolds. Included in this theorem is the Poincaré conjecture, which states that any closed, simply connected three-manifold is homeomorphic (and in fact diffeomorphic) to the 3-sphere.

Beginning in dimension 4, the classification becomes much more difficult for two reasons. Firstly, every finitely presented group appears as the fundamental group of some 4-manifold, and since the fundamental group is a diffeomorphism invariant, this makes the classification of 4-manifolds at least as difficult as the classification of finitely presented groups. By the word problem for groups, which is equivalent to the halting problem, it is impossible to classify such groups, so a full topological classification is impossible. Secondly, beginning in dimension four it is possible to have smooth manifolds that are homeomorphic, but with distinct, non-diffeomorphic smooth structures. This is true even for the Euclidean space $$\mathbb{R}^4$$, which admits many exotic $\mathbb{R}^4$ structures. This means that the study of differential topology in dimensions 4 and higher must use tools genuinely outside the realm of the regular continuous topology of topological manifolds. One of the central open problems in differential topology is the four-dimensional smooth Poincaré conjecture, which asks if every smooth 4-manifold that is homeomorphic to the 4-sphere, is also diffeomorphic to it. That is, does the 4-sphere admit only one smooth structure? This conjecture is true in dimensions 1, 2, and 3, by the above classification results, but is known to be false in dimension 7 due to the Milnor spheres.

Important tools in studying the differential topology of smooth manifolds include the construction of smooth topological invariants of such manifolds, such as de Rham cohomology or the intersection form, as well as smoothable topological constructions, such as smooth surgery theory or the construction of cobordisms. Morse theory is an important tool which studies smooth manifolds by considering the critical points of differentiable functions on the manifold, demonstrating how the smooth structure of the manifold enters into the set of tools available. Oftentimes more geometric or analytical techniques may be used, by equipping a smooth manifold with a Riemannian metric or by studying a differential equation on it. Care must be taken to ensure that the resulting information is insensitive to this choice of extra structure, and so genuinely reflects only the topological properties of the underlying smooth manifold. For example, the Hodge theorem provides a geometric and analytical interpretation of the de Rham cohomology, and gauge theory was used by Simon Donaldson to prove facts about the intersection form of simply connected 4-manifolds. In some cases techniques from contemporary physics may appear, such as topological quantum field theory, which can be used to compute topological invariants of smooth spaces.

Famous theorems in differential topology include the Whitney embedding theorem, the hairy ball theorem, the Hopf theorem, the Poincaré–Hopf theorem, Donaldson's theorem, and the Poincaré conjecture.

Description
Differential topology considers the properties and structures that require only a smooth structure on a manifold to be defined. Smooth manifolds are 'softer' than manifolds with extra geometric structures, which can act as obstructions to certain types of equivalences and deformations that exist in differential topology. For instance, volume and Riemannian curvature are invariants that can distinguish different geometric structures on the same smooth manifold—that is, one can smoothly "flatten out" certain manifolds, but it might require distorting the space and affecting the curvature or volume.

On the other hand, smooth manifolds are more rigid than the topological manifolds. John Milnor discovered that some spheres have more than one smooth structure—see Exotic sphere and Donaldson's theorem. Michel Kervaire exhibited topological manifolds with no smooth structure at all. Some constructions of smooth manifold theory, such as the existence of tangent bundles, can be done in the topological setting with much more work, and others cannot.

One of the main topics in differential topology is the study of special kinds of smooth mappings between manifolds, namely immersions and submersions, and the intersections of submanifolds via transversality. More generally one is interested in properties and invariants of smooth manifolds that are carried over by diffeomorphisms, another special kind of smooth mapping. Morse theory is another branch of differential topology, in which topological information about a manifold is deduced from changes in the rank of the Jacobian of a function.

For a list of differential topology topics, see the following reference: List of differential geometry topics.

Differential topology versus differential geometry
Differential topology and differential geometry are first characterized by their similarity. They both study primarily the properties of differentiable manifolds, sometimes with a variety of structures imposed on them.

One major difference lies in the nature of the problems that each subject tries to address. In one view, differential topology distinguishes itself from differential geometry by studying primarily those problems that are inherently global. Consider the example of a coffee cup and a donut. From the point of view of differential topology, the donut and the coffee cup are the same (in a sense). This is an inherently global view, though, because there is no way for the differential topologist to tell whether the two objects are the same (in this sense) by looking at just a tiny (local) piece of either of them. They must have access to each entire (global) object.

From the point of view of differential geometry, the coffee cup and the donut are different because it is impossible to rotate the coffee cup in such a way that its configuration matches that of the donut. This is also a global way of thinking about the problem. But an important distinction is that the geometer does not need the entire object to decide this. By looking, for instance, at just a tiny piece of the handle, they can decide that the coffee cup is different from the donut because the handle is thinner (or more curved) than any piece of the donut.

To put it succinctly, differential topology studies structures on manifolds that, in a sense, have no interesting local structure. Differential geometry studies structures on manifolds that do have an interesting local (or sometimes even infinitesimal) structure.

More mathematically, for example, the problem of constructing a diffeomorphism between two manifolds of the same dimension is inherently global since locally two such manifolds are always diffeomorphic. Likewise, the problem of computing a quantity on a manifold that is invariant under differentiable mappings is inherently global, since any local invariant will be trivial in the sense that it is already exhibited in the topology of $$\R^n$$. Moreover, differential topology does not restrict itself necessarily to the study of diffeomorphism. For example, symplectic topology—a subbranch of differential topology—studies global properties of symplectic manifolds. Differential geometry concerns itself with problems—which may be local or global—that always have some non-trivial local properties. Thus differential geometry may study differentiable manifolds equipped with a connection, a metric (which may be Riemannian, pseudo-Riemannian, or Finsler), a special sort of distribution (such as a CR structure), and so on.

This distinction between differential geometry and differential topology is blurred, however, in questions specifically pertaining to local diffeomorphism invariants such as the tangent space at a point. Differential topology also deals with questions like these, which specifically pertain to the properties of differentiable mappings on $$\R^n$$ (for example the tangent bundle, jet bundles, the Whitney extension theorem, and so forth).

The distinction is concise in abstract terms:
 * Differential topology is the study of the (infinitesimal, local, and global) properties of structures on manifolds that have only trivial local moduli.
 * Differential geometry is such a study of structures on manifolds that have one or more non-trivial local moduli.

title: Differential topology


text:
Talk:Data structure

Routing tables
Can someone who is a little more familiar with routing tables as data structures take the initiative to clarify this sentence?
 * For example, B-trees are particularly well-suited for implementation of databases, while routing tables rely on networks of machines to function.

The linked article does not really discuss routing tables as a data structure so much as it examines their role in the network ecosystem. "while routing tables enable networks of machines to function" describes their function better, it doesn't really say anything about routing tables as data structures. Perhaps another example altogether would be better?

--gortsack 18:24, 18 April 2006 (UTC)

Haphazard Categorization
My categorization scheme for the links from this page is rather haphazard. If anyone has good ideas on how to organize it, be bold. --BlckKnght

It may be even more haphazard now. Just moved to this page the section on "data tables and functions" from the structure page. It was way too complex for that other page. I didn't attempt to merge it with the prior info on this page, but this is probably needed. --Panchobook (talk) 23:40, 23 June 2011 (UTC)

Desktop file browser dream
(omitted discussion of my dream of how a Desktop File Browser and integrated Web Browser should be designed) brettz9

 * Hi Brett, you raise some interesting points here; what would make things a bit closer to this vision is a better file browser widget for Mozilla, but who knows if/when this will happen. Anyway, since this text represents your own philosophy, it cannot follow Wikipedia's neutral point of view policy. The place for this article is on the Meta-Wikipedia. -- Merphant 12:52 Jan 21, 2003 (UTC)

Thanks for the suggestions...However, as far as I could tell, Meta-Wikipedia seemed just concerned about general things of concern to Wikipedia itself rather than its specific content.

I was also told that it was all right to put opinions and such in the discuss pages such as this.

 * On further reflection, I have come to the thought that discuss pages should probably be limited to debating the content that is appropriate at the site even if opinions are permitted (in order to allow for this discussion to take place without too many distractions). Maybe in the absence of a universal categorized wiki site for sharing idea and invention concepts, a person could just put an external link at the wikipedia page in question (leading to an individual's wiki site or Usenet discussion, etc. dedicated to sharing ideas on that wikipedia page's topic (e.g., computer science)) brettz9

List of data structures
I changed the line "This is an incomplete list of data structures:", because it is unprofessionial. —Noldoaran (Talk) 22:15, Feb 14, 2004 (UTC)

In line with standard practice here, the list of data structures should be a free-standing page, separate from this one.

Charles Matthews 09:52, 3 May 2004 (UTC)

 * Right. What holds you up to do so? Anyway, I have separated the list. -- Taku 10:02, May 3, 2004 (UTC)

Node merge
The article on Node_(computer_science) contains little info. Ripper234 20:29, 2 April 2006 (UTC)

DEAR WIKIPEDIA PPL. perhaps you should tell me what the fuck a NODE IS instead of telling me that it links to other shit and does other shit. —The preceding unsigned comment was added by 140.180.153.198 (talk • contribs) 04:24, 6 April 2006 (UTC).

DEAR UNINFORMED IDIOT. something that 'links to shit and does other shit' is exactly 'what the fuck' a node is. enjoy —The preceding unsigned comment was added by 81.132.20.207 (talk • contribs) 13:28, 8 April 2006 (UTC).

I'm un-merging the node article. 140.180.153.198 has a point, that nodes themselves deserve an explanation. --Snarius 23:33, 3 August 2006 (UTC)

Link removal
SOMEONE removed this important link http://www.alnaja7.org/Programmer/215/ITCS_215.htm, is there any reason ??Alhoori 19:01, 20 May 2006 (UTC)
 * It's a link to your personal site; your recent edits suggest that you are trying to use Wikipedia to promote it. Can you explain why you think it's so important?  OhNo itsJamie Talk 20:27, 20 May 2006 (UTC)

 * Do you know data structure ? can you give me an easy explanation of it ? why you don't like others to benefit from any information ? did you read the links ? did you see how easy they are explained ? If you can explain the data structure topic easier than that, then please remove my link ! Alhoori 21:45, 20 May 2006 (UTC)
 * Yes, as a matter of fact, I use standard Java data structures (and write custom ones) on a daily basis. This article (and the few .edu external links) explain them just fine for an encyclopedia article. Once again, WIkipedia is not a vehicle to promote your personal website.  OhNo  itsJamie Talk 22:00, 20 May 2006 (UTC)

 * Until now u didn't give a good reason, why you removed the links . Does it matter if a useful personal site ? why don't you do a useful tutorial so that you add it ? I taught DS course for 3 years , so I believe this tutorial should be there . Moreover , it already was there for around 2 months ago , until the site have problems 2 days ago . Alhoori 01:12, 21 May 2006 (UTC)

If the content is good it should be there. I haven't checked it, though.

Link removal
Please tell me what is wrong about the following link which is removed 3 times? C#, Python, Ruby
 * Bruno R. Preiss, Data Structures and Algorithms with Object-Oriented Design Patterns in C++, Java,

I am not promoting anything and I don't know the author either. This is just a useful link to some valuable academic content, and the author has put his work freely for people to use and learn. So what is undesirable for you about it that you remove it everytime?

If you're going to remove it again, please also give an answer here. Previous unsigned comment by Special:Contributions/69.108.125.234

Alternative definition
data structure is a collection of d,f,a.means that D(Domain),F(Function),A(Axioms) D=this is the range of values that the data may have.this domain is also termed as data object. F=this is set of operation which may legally be applied to elements of data object.this implies that for a data structure we must specified the set of operations. A=this is the set of rules with which the different operation belongs to F actually can be implemented. —The preceding unsigned comment was added by Special:Contributions/ (talk)
 * This is *one* possible definition of *abstract* data *type*, a concept of formal semantics or type theory that aims to hide the implementation and machine details. A data *structure* is a "concrete" concept, that makes sense even for assembly- or machine-language and where implementation details are essential. All the best, --Jorge Stolfi (talk) 05:10, 28 January 2010 (UTC)
 * I am not happy with the confusion of data structures and data types in the article. Data structures and data types are different things. Furthermore, with abstract data types, data structures are not implicitly defined either - they are not defined at all, at least not from the client point of view. However, data structures are used to implement (abstract) data types. If people agree with this view, I can edit the article. Rehms (talk) 15:57, 31 August 2014 (UTC)

Vague tags
The following editorial tags were added to this article:

Would the editor please be more specific? (Note that if a statement about XXX includes a wikilink to the XXX article, and that article makes the same statement with a reference, then the first statement is not "unreferenced".) Thanks, and all the best, --Jorge Stolfi (talk) 05:03, 28 January 2010 (UTC)

Data structure support in IBM/360 assembly language
Someone tagged as the assertion that "Assembly languages generally lack support for data structures", noting (in an invisible comment) that "IBM/360 didn't lack support 40 years ago". Perhaps the statement was ambiguous; what was meant is that A.L. do not generally provide special syntax for complex data structures such as arrays and lists. Obviously they do provide syntax for bulk storage allocation, indexing and address computation. Features that are implemented through macro libraries do not count as *language* features. (By comparison, the C language provides facilities for arrays and records, but not for linked lists or trees --- even though one can implement such data structures in C as library types and procedures.) Does this answer the comment? Should the sentence be reworded for clarity? All the best, --Jorge Stolfi (talk) 12:55, 1 February 2010 (UTC)
 * The OS/360 and successor assemblers provide DSECT, which is a way to give symbolic names to offsets. They are commonly used with the data structures of OS/360 itself, especially the DCB. A DSECT assembles pretty much the same way as a CSECT (actual code or data to be generated) but doesn't generate any object program. This works naturally with the base-displacement addressing of S/360, as you point a register somewhere, and tell the assembler which data structure to use, to generate offsets. I would expect that this would have been copied into other assemblers, but I haven't tried them all. OS/360 is getting close to 60 years old now. Maybe it still isn't most, though. Gah4 (talk) 19:51, 30 August 2023 (UTC)
 * The OS/360 and successor assemblers provide DSECT, which is a way to give symbolic names to offsets. They are commonly used with the data structures of OS/360 itself, especially the DCB. A DSECT assembles pretty much the same way as a CSECT (actual code or data to be generated) but doesn't generate any object program. This works naturally with the base-displacement addressing of S/360, as you point a register somewhere, and tell the assembler which data structure to use, to generate offsets. I would expect that this would have been copied into other assemblers, but I haven't tried them all. OS/360 is getting close to 60 years old now. Maybe it still isn't most, though. Gah4 (talk) 19:51, 30 August 2023 (UTC)

List of data structures
Can we include in the article a list of the more common data structures: array, linked list, hash table, B-tree, heap, graph represented as a matrix, graph represented as a list. Any others? We should make a table of their insertion and removal running times and overhead running space. -Pgan002 (talk) 08:52, 3 March 2011 (UTC)
 * Why is the linked list not included in "Overview"?

Stack, Queue Manihass CH (talk) 02:46, 23 February 2023 (UTC)

Values are not retrieved from sets
The statement that values are not retrieved from sets is wrong. The HashSet class in Java for example is a concrete implementation of a set which returns values in it, as does the similarly named class in C#.

Overview clarification
In the Overview, we currently have: "An object contains data fields, like a record, and also contains program code fragments for accessing or modifying those fields. Data structures not containing code, like those above, are called plain old data structures."

Would it be worth clarifying, that while this is a valid sentence, it really applies in the context of object-oriented programming (which is not the be-all and end-all of programming)? Something like, "In the context of [object-oriented programming], ..."

Chris Alexander UK (talk) 19:49, 19 May 2014 (UTC)

 * Hello there! To me, that sounds like a good improvement. — Dsimic (talk | contribs) 06:27, 23 May 2014 (UTC)

Databases example
This revision changed the wording of the 2nd paragraph from
 * ''For example, B-trees are particularly well-suited for implementation of databases, while compiler implementations usually use hash tables to look up identifiers.

to
 * ''For example, databases use B-tree indexes for small percentages of data retrieval and compilers and databases use dynamic hash tables as look up tables.

It this true? I would say B-tree (or other types of binary tree) indexes are most commonly used. --Jvs (talk) 10:51, 24 December 2015 (UTC)
 * Whether or not it's true, it seems ambiguous to me. "Small percentages" could mean a small fraction of the queries, or it could mean queries that return a small fraction of the data. —David Eppstein (talk) 15:31, 24 December 2015 (UTC)

Data structure vs data type
I'm not an expert in computer science, but here is just a remark about something I find confusing and might confuse other readers. In the beginning of the article it says Not to be confused with data type, but in my opinion the difference between the two is not explained, thus it should be pointed out where the difference between the two is. Also it says in the article Data structures serve as the basis for abstract data types, this makes it even more unclear. The wikipedia article on abstract data types contains a list of examples of abstract data types such as "Tree", but if one clicks at this link one gets to the page Tree (data structure). In contrast to that, for some data structures/types there are two separate articles. For instance, there is an article on "Array data type" and "Array data structure". I have the feeling that "data type" tends to be more related to programming language whereas "data structure" tends to be more about the concept itself, but if this is the case, then it should be clearly stated somewhere. Zaunlen (talk) 17:17, 2 August 2019 (UTC)

Data Structure

The Logical or mathmatical model of particular organization of data is called as data structure.

data structure operation

→data appearing in our data structure is processed by means of certain operations. →1) traversing- accessing each record exactly once so that certain items in the record may be processed.(visiting the record). →2) Searching - Finding the location of the record with a given key value, or finding the location of all records which satisfy one or more condition.

Efficiency
I am surprised that the article defines data structures as efficient. Obviously different data structures may be optimized for different goals, but as far as I remember from CS class a data structure is still a data structure even if it's really inefficient. Do most RS really say that an inefficient data structure isn't? (t · c)  buidhe  06:24, 21 June 2022 (UTC)
 * I certainly wouldn't consider efficiency a necessary part of the definition, although both measurement of efficiency and design for efficiency are very important for this topic, and I guess my own lecture notes do include efficiency on their "What is a data structure" slide. Pat Morin's open-access textbook leads with efficiency (section 1.1) but doesn't appear to provide a definition for what a data structure is. Brass's Advanced Data Structures says that "A data structure is a method1 to realize a set of operations on some data"; no mention of efficiency. Those were the references that were easiest for me to check; I haven't looked at others recently. —David Eppstein (talk) 06:36, 21 June 2022 (UTC)
 * @Buidhe Choosing the correct data structure for some goal is an important problem, if incorrect data structure is chosen, then it is not efficient. You are right that "incorrect chosen data structure" is still a data structure. But let me use a metaphor, "All tables has four legs", now a three legged isn't a table? No, it is still a table, but it is an incorrect table. By this metaphor, data structure here means a "Correctly chosen data structure". Good luck, Hooman Mallahzadeh (talk) 06:41, 21 June 2022 (UTC)
 * I suggest to change the sentence to
 * "In computer science, a data structure is a data organization, management, and storage format that when correctly chosen enables efficient access and modification."

 * Without bolding any part. Do you agree? Hooman Mallahzadeh (talk) 06:44, 21 June 2022 (UTC)
 * "Correctly" is a strong word, implying that one choice is correct and others are not, when often there are tradeoffs. "well chosen" would be better. But in any case, it misses the point here, which is that however you choose to organize your data, or not, you have chosen a data structure. If you want a priority queue, then an unordered list of items and priorities is an example. It's usually not very efficient compared to alternatives like the binary heap, but it is still a data structure. And sometimes (for instance in Prim's algorithm for dense graphs) it may even be a good choice. —David Eppstein (talk) 06:53, 21 June 2022 (UTC)

India Education Program course assignment
This article was the subject of an educational assignment supported by Wikipedia Ambassadors through the India Education Program.

The above message was substituted from by PrimeBOT (talk) on 19:52, 1 February 2023 (UTC)

Wiki Education assignment: Research Process and Methodology - FA23 - Sect 201 - Thu
— Assignment last updated by Harrisondonnersbach (talk) 04:17, 12 November 2023 (UTC)

"Active data structure" listed at Redirects for discussion
The redirect [//en.wikipedia.org/w/index.php?title=Active_data_structure&redirect=no Active data structure] has been listed at redirects for discussion to determine whether its use and function meets the redirect guidelines. Readers of this page are welcome to comment on this redirect at  until a consensus is reached. Utopes (talk / cont) 22:05, 20 March 2024 (UTC)

title: Talk:Data structure


text:
Diffeomorphism

In mathematics, a diffeomorphism is an isomorphism of differentiable manifolds. It is an invertible function that maps one differentiable manifold to another such that both the function and its inverse are continuously differentiable.

Definition
Given two differentiable manifolds $$M$$ and $$N$$, a differentiable map $$f \colon M \rightarrow N $$ is a diffeomorphism if it is a bijection and its inverse $$f^{-1} \colon N \rightarrow M$$ is differentiable as well. If these functions are $$r$$ times continuously differentiable, $$f$$ is called a $$C^r$$-diffeomorphism.

Two manifolds $$M$$ and $$N$$ are diffeomorphic (usually denoted $$M \simeq N$$) if there is a diffeomorphism $$f$$  from $$M$$ to $$N$$. Two $$C^r$$-differentiable manifolds are $$C^r$$-diffeomorphic if there is an $$ r $$ times continuously differentiable bijective map between them whose inverse is also $$r$$ times continuously differentiable.

Diffeomorphisms of subsets of manifolds
Given a subset $$X$$ of a manifold $$M$$ and a subset $$Y$$ of a manifold $$N$$, a function $$f:X\to Y$$ is said to be smooth if for all $$p$$ in $$X$$ there is a neighborhood $$U\subset M$$ of $$p$$ and a smooth function $$g:U\to N$$ such that the restrictions agree: $$g_{|U \cap X} = f_{|U \cap X}$$ (note that $$g$$ is an extension of $$f$$). The function $$f$$ is said to be a diffeomorphism if it is bijective, smooth and its inverse is smooth.

Local description
Testing whether a differentiable map is a diffeomorphism can be made locally under some mild restrictions. This is the Hadamard-Caccioppoli theorem:

If $$U$$, $$V$$ are connected open subsets of $$\R^n$$ such that $$V$$ is simply connected, a differentiable map $$f:U\to V$$ is a diffeomorphism if it is proper and if the differential $$Df_x:\R^n\to\R^n$$ is bijective (and hence a linear isomorphism) at each point $$x$$ in $$U$$.

Some remarks:

It is essential for $$V$$ to be simply connected for the function $$f$$ to be globally invertible (under the sole condition that its derivative be a bijective map at each point). For example, consider the "realification" of the complex square function
 * $$\begin{cases}

f : \R^2 \setminus \{(0,0)\} \to \R^2 \setminus \{(0,0)\} \\ (x,y)\mapsto(x^2-y^2,2xy). \end{cases}$$ Then $$f$$ is surjective and it satisfies
 * $$\det Df_x = 4(x^2+y^2) \neq 0.$$

Thus, though $$Df_x$$ is bijective at each point, $$f$$ is not invertible because it fails to be injective (e.g. $$f(1,0)=(1,0)=f(-1,0)$$).

Since the differential at a point (for a differentiable function)
 * $$Df_x : T_xU \to T_{f(x)}V$$

is a linear map, it has a well-defined inverse if and only if $$Df_x$$ is a bijection. The matrix representation of $$Df_x$$ is the $$n\times n$$ matrix of first-order partial derivatives whose entry in the $$i$$-th row and $$j$$-th column is $$\partial f_i / \partial x_j$$. This so-called Jacobian matrix is often used for explicit computations.

Diffeomorphisms are necessarily between manifolds of the same dimension. Imagine $$f$$ going from dimension $$n$$ to dimension $$k$$. If $$nk$$ then $$Df_x$$ could never be injective. In both cases, therefore, $$Df_x$$ fails to be a bijection.

If $$Df_x$$ is a bijection at $$x$$ then $$f$$ is said to be a local diffeomorphism (since, by continuity, $$Df_y$$ will also be bijective for all $$y$$ sufficiently close to $$x$$).

Given a smooth map from dimension $$n$$ to dimension $$k$$, if $$Df$$ (or, locally, $$Df_x$$) is surjective, $$f$$ is said to be a submersion (or, locally, a "local submersion"); and if $$Df$$ (or, locally, $$Df_x$$) is injective, $$f$$ is said to be an immersion (or, locally, a "local immersion").

A differentiable bijection is not necessarily a diffeomorphism. $$f(x)=x^3$$, for example, is not a diffeomorphism from $$\R$$ to itself because its derivative vanishes at 0 (and hence its inverse is not differentiable at 0). This is an example of a homeomorphism that is not a diffeomorphism.

When $$f$$ is a map between differentiable manifolds, a diffeomorphic $$f$$ is a stronger condition than a homeomorphic $$f$$. For a diffeomorphism, $$f$$ and its inverse need to be differentiable; for a homeomorphism, $$f$$ and its inverse need only be continuous. Every diffeomorphism is a homeomorphism, but not every homeomorphism is a diffeomorphism.

$$f:M\to N$$ is a diffeomorphism if, in coordinate charts, it satisfies the definition above. More precisely: Pick any cover of $$M$$ by compatible coordinate charts and do the same for $$N$$. Let $$\phi$$ and $$\psi$$ be charts on, respectively, $$M$$ and $$N$$, with $$U$$ and $$V$$ as, respectively, the images of $$\phi$$ and $$\psi$$. The map $$\psi f\phi^{-1}:U\to V$$ is then a diffeomorphism as in the definition above, whenever $$f(\phi^{-1}(U))\subseteq\psi^{-1}(V)$$.

Examples
Since any manifold can be locally parametrised, we can consider some explicit maps from $$\R^2$$ into $$\R^2$$.

 * Let
 * $$f(x,y) = \left (x^2 + y^3, x^2 - y^3 \right ).$$
 * We can calculate the Jacobian matrix:
 * $$ J_f = \begin{pmatrix} 2x & 3y^2 \\ 2x & -3y^2 \end{pmatrix} . $$
 * The Jacobian matrix has zero determinant if and only if $$xy=0$$. We see that $$f$$ could only be a diffeomorphism away from the $$x$$-axis and the $$y$$-axis. However, $$f$$ is not bijective since $$f(x,y)=f(-x,y)$$, and thus it cannot be a diffeomorphism.

 * Let
 * $$g(x,y) = \left (a_0 + a_{1,0}x + a_{0,1}y + \cdots, \ b_0 + b_{1,0}x + b_{0,1}y + \cdots \right )$$
 * where the $$a_{i,j}$$ and $$b_{i,j}$$ are arbitrary real numbers, and the omitted terms are of degree at least two in x and y. We can calculate the Jacobian matrix at 0:
 * $$ J_g(0,0) = \begin{pmatrix} a_{1,0} & a_{0,1} \\ b_{1,0} & b_{0,1} \end{pmatrix}. $$
 * We see that g is a local diffeomorphism at 0 if, and only if,
 * $$a_{1,0}b_{0,1} - a_{0,1}b_{1,0} \neq 0,$$
 * i.e. the linear terms in the components of g are linearly independent as polynomials.

 * Let
 * $$h(x,y) = \left (\sin(x^2 + y^2), \cos(x^2 + y^2) \right ).$$
 * We can calculate the Jacobian matrix:
 * $$ J_h = \begin{pmatrix} 2x\cos(x^2 + y^2) & 2y\cos(x^2 + y^2) \\ -2x\sin(x^2+y^2) & -2y\sin(x^2 + y^2) \end{pmatrix} . $$
 * The Jacobian matrix has zero determinant everywhere! In fact we see that the image of h is the unit circle.

Surface deformations
In mechanics, a stress-induced transformation is called a deformation and may be described by a diffeomorphism. A diffeomorphism $$f:U\to V$$ between two surfaces $$U$$ and $$V$$ has a Jacobian matrix $$Df$$ that is an invertible matrix. In fact, it is required that for $$p$$ in $$U$$, there is a neighborhood of $$p$$ in which the Jacobian $$Df$$ stays non-singular. Suppose that in a chart of the surface, $$f(x,y) = (u,v).$$

The total differential of u is
 * $$du = \frac{\partial u}{\partial x} dx + \frac{\partial u}{\partial y} dy$$, and similarly for v.

Then the image $$ (du, dv) = (dx, dy) Df $$ is a linear transformation, fixing the origin, and expressible as the action of a complex number of a particular type. When (dx, dy) is also interpreted as that type of complex number, the action is of complex multiplication in the appropriate complex number plane. As such, there is a type of angle (Euclidean, hyperbolic, or slope) that is preserved in such a multiplication. Due to Df being invertible, the type of complex number is uniform over the surface. Consequently, a surface deformation or diffeomorphism of surfaces has the conformal property of preserving (the appropriate type of) angles.

Diffeomorphism group
Let $$M$$ be a differentiable manifold that is second-countable and Hausdorff. The diffeomorphism group of $$M$$ is the group of all $$C^r$$ diffeomorphisms of $$M$$ to itself, denoted by $$\text{Diff}^r(M)$$ or, when $$r$$ is understood, $$\text{Diff}(M)$$. This is a "large" group, in the sense that—provided $$M$$ is not zero-dimensional—it is not locally compact.

Topology
The diffeomorphism group has two natural topologies: weak and strong. When the manifold is compact, these two topologies agree. The weak topology is always metrizable. When the manifold is not compact, the strong topology captures the behavior of functions "at infinity" and is not metrizable. It is, however, still Baire.

Fixing a Riemannian metric on $$M$$, the weak topology is the topology induced by the family of metrics
 * $$d_K(f,g) = \sup\nolimits_{x\in K} d(f(x),g(x)) + \sum\nolimits_{1\le p\le r} \sup\nolimits_{x\in K} \left \|D^pf(x) - D^pg(x) \right \|$$

as $$K$$ varies over compact subsets of $$M$$. Indeed, since $$M$$ is $$\sigma$$-compact, there is a sequence of compact subsets $$K_n$$ whose union is $$M$$. Then:
 * $$d(f,g) = \sum\nolimits_n 2^{-n}\frac{d_{K_n}(f,g)}{1+d_{K_n}(f,g)}.$$

The diffeomorphism group equipped with its weak topology is locally homeomorphic to the space of $$C^r$$ vector fields. Over a compact subset of $$M$$, this follows by fixing a Riemannian metric on $$M$$ and using the exponential map for that metric. If $$r$$ is finite and the manifold is compact, the space of vector fields is a Banach space. Moreover, the transition maps from one chart of this atlas to another are smooth, making the diffeomorphism group into a Banach manifold with smooth right translations; left translations and inversion are only continuous. If $$r=\infty$$, the space of vector fields is a Fréchet space. Moreover, the transition maps are smooth, making the diffeomorphism group into a Fréchet manifold and even into a regular Fréchet Lie group. If the manifold is $$\sigma$$-compact and not compact the full diffeomorphism group is not locally contractible for any of the two topologies. One has to restrict the group by controlling the deviation from the identity near infinity to obtain a diffeomorphism group which is a manifold; see.

Lie algebra
The Lie algebra of the diffeomorphism group of $$M$$ consists of all vector fields on $$M$$ equipped with the Lie bracket of vector fields. Somewhat formally, this is seen by making a small change to the coordinate $$x$$ at each point in space:
 * $$x^{\mu} \mapsto x^{\mu} + \varepsilon h^{\mu}(x)$$

so the infinitesimal generators are the vector fields
 * $$ L_{h} = h^{\mu}(x)\frac{\partial}{\partial x^\mu}.$$

Examples

 * When $$M=G$$ is a Lie group, there is a natural inclusion of $$G$$ in its own diffeomorphism group via left-translation. Let $$\text{Diff}(G)$$ denote the diffeomorphism group of $$G$$, then there is a splitting $$\text{Diff}(G)\simeq G\times\text{Diff}(G,e)$$, where $$\text{Diff}(G,e)$$ is the subgroup of $$\text{Diff}(G)$$ that fixes the identity element of the group.
 * The diffeomorphism group of Euclidean space $$\R^n$$ consists of two components, consisting of the orientation-preserving and orientation-reversing diffeomorphisms. In fact, the general linear group is a deformation retract of the subgroup $$\text{Diff}(\R^n,0)$$ of diffeomorphisms fixing the origin under the map $$f(x)\to f(tx)/t, t\in(0,1]$$. In particular, the general linear group is also a deformation retract of the full diffeomorphism group.
 * For a finite set of points, the diffeomorphism group is simply the symmetric group. Similarly, if $$M$$ is any manifold there is a group extension $$0\to\text{Diff}_0(M)\to\text{Diff}(M)\to\Sigma(\pi_0(M))$$. Here $$\text{Diff}_0(M)$$ is the subgroup of $$\text{Diff}(M)$$ that preserves all the components of $$M$$, and $$\Sigma(\pi_0(M))$$ is the permutation group of the set $$\pi_0(M)$$ (the components of $$M$$). Moreover, the image of the map $$\text{Diff}(M)\to\Sigma(\pi_0(M))$$ is the bijections of $$\pi_0(M)$$ that preserve diffeomorphism classes.

Transitivity
For a connected manifold $$M$$, the diffeomorphism group acts transitively on $$M$$. More generally, the diffeomorphism group acts transitively on the configuration space $$C_k M$$. If $$M$$ is at least two-dimensional, the diffeomorphism group acts transitively on the configuration space $$F_k M$$ and the action on $$M$$ is multiply transitive.

Extensions of diffeomorphisms
In 1926, Tibor Radó asked whether the harmonic extension of any homeomorphism or diffeomorphism of the unit circle to the unit disc yields a diffeomorphism on the open disc. An elegant proof was provided shortly afterwards by Hellmuth Kneser. In 1945, Gustave Choquet, apparently unaware of this result, produced a completely different proof.

The (orientation-preserving) diffeomorphism group of the circle is pathwise connected. This can be seen by noting that any such diffeomorphism can be lifted to a diffeomorphism $$f$$ of the reals satisfying $$[f(x+1)=f(x)+1]$$; this space is convex and hence path-connected. A smooth, eventually constant path to the identity gives a second more elementary way of extending a diffeomorphism from the circle to the open unit disc (a special case of the Alexander trick). Moreover, the diffeomorphism group of the circle has the homotopy-type of the orthogonal group $$O(2)$$.

The corresponding extension problem for diffeomorphisms of higher-dimensional spheres $$S^{n-1}$$ was much studied in the 1950s and 1960s, with notable contributions from René Thom, John Milnor and Stephen Smale. An obstruction to such extensions is given by the finite abelian group $$\Gamma_n$$, the "group of twisted spheres", defined as the quotient of the abelian component group of the diffeomorphism group by the subgroup of classes extending to diffeomorphisms of the ball $$B^n$$.

Connectedness
For manifolds, the diffeomorphism group is usually not connected. Its component group is called the mapping class group. In dimension 2 (i.e. surfaces), the mapping class group is a finitely presented group generated by Dehn twists; this has been proved by Max Dehn, W. B. R. Lickorish, and Allen Hatcher). Max Dehn and Jakob Nielsen showed that it can be identified with the outer automorphism group of the fundamental group of the surface.

William Thurston refined this analysis by classifying elements of the mapping class group into three types: those equivalent to a periodic diffeomorphism; those equivalent to a diffeomorphism leaving a simple closed curve invariant; and those equivalent to pseudo-Anosov diffeomorphisms. In the case of the torus $$S^1\times S^1=\R^2/\Z^2$$, the mapping class group is simply the modular group $$\text{SL}(2,\Z)$$ and the classification becomes classical in terms of elliptic, parabolic and hyperbolic matrices. Thurston accomplished his classification by observing that the mapping class group acted naturally on a compactification of Teichmüller space; as this enlarged space was homeomorphic to a closed ball, the Brouwer fixed-point theorem became applicable. Smale conjectured that if $$M$$ is an oriented smooth closed manifold, the identity component of the group of orientation-preserving diffeomorphisms is simple. This had first been proved for a product of circles by Michel Herman; it was proved in full generality by Thurston.

Homotopy types

 * The diffeomorphism group of $$S^2$$ has the homotopy-type of the subgroup $$O(3)$$. This was proven by Steve Smale.
 * The diffeomorphism group of the torus has the homotopy-type of its linear automorphisms: $$S^1\times S^1\times\text{GL}(2,\Z)$$.
 * The diffeomorphism groups of orientable surfaces of genus $$g>1$$ have the homotopy-type of their mapping class groups (i.e. the components are contractible).
 * The homotopy-type of the diffeomorphism groups of 3-manifolds are fairly well understood via the work of Ivanov, Hatcher, Gabai and Rubinstein, although there are a few outstanding open cases (primarily 3-manifolds with finite fundamental groups).
 * The homotopy-type of diffeomorphism groups of $$n$$-manifolds for $$n>3$$ are poorly understood. For example, it is an open problem whether or not $$\text{Diff}(S^4)$$ has more than two components. Via Milnor, Kahn and Antonelli, however, it is known that provided $$n>6$$, $$\text{Diff}(S^n)$$ does not have the homotopy-type of a finite CW-complex.

Homeomorphism and diffeomorphism
Since every diffeomorphism is a homeomorphism, given a pair of manifolds which are diffeomorphic to each other they are in particular homeomorphic to each other. The converse is not true in general.

While it is easy to find homeomorphisms that are not diffeomorphisms, it is more difficult to find a pair of homeomorphic manifolds that are not diffeomorphic. In dimensions 1, 2 and 3, any pair of homeomorphic smooth manifolds are diffeomorphic. In dimension 4 or greater, examples of homeomorphic but not diffeomorphic pairs exist. The first such example was constructed by John Milnor in dimension 7. He constructed a smooth 7-dimensional manifold (called now Milnor's sphere) that is homeomorphic to the standard 7-sphere but not diffeomorphic to it. There are, in fact, 28 oriented diffeomorphism classes of manifolds homeomorphic to the 7-sphere (each of them is the total space of a fiber bundle over the 4-sphere with the 3-sphere as the fiber).

More unusual phenomena occur for 4-manifolds. In the early 1980s, a combination of results due to Simon Donaldson and Michael Freedman led to the discovery of exotic $$\R^4$$: there are uncountably many pairwise non-diffeomorphic open subsets of $$\R^4$$ each of which is homeomorphic to $$\R^4$$, and also there are uncountably many pairwise non-diffeomorphic differentiable manifolds homeomorphic to $$\R^4$$ that do not embed smoothly in $$\R^4$$.

title: Diffeomorphism